Comprendre la complexité algorithmique (notation Big-O) ?

Quand on analyse les performances d'un algorithme, on utilise la notation de Landau (souvent appelée “Big-O”) pour exprimer la complexité algorithmique.

Cette notation permet d’évaluer comment le temps d’exécution évolue en fonction de la taille de l’entrée.

Voyons ce que cela signifie, et les différences entre des complexités comme O(n), O(n²) et O(log(n)).

La notation

Dans la notation O(n) :

• O représente la complexité de la fonction que nous évaluons
• n représente le nombre de d’itérations que notre code va devoir effectuer avant de s’arrêter

Par exemple, pour parcourir une liste de 3 éléments [”a”, “b”, “c”], on devra exécuter une boucle de 3 itérations.

Alors la complexité pour parcourir l’entièreté de la liste sera de O(3).

Sauf qu’en pratique, pour les algorithmes dont l’efficacité est importante, on ne connait pas à l’avance le nombre d’élément à traiter, on utilise la variable n !

Pour résumer, si n est le nombre d’élément d’une liste, alors si l’on doit parcourir chaque élément de la liste, la complexité de cet algorithme sera O(n).

Vous l’aurez compris, notre objectif est de faire en sorte que la complexité de notre algorithme n’augmente pas aussi vite que le nombre d’éléments à traiter…

Mais ce n’est pas toujours possible !

Nous allons voir ensemble quelques exemples de complexité à connaitre et à comprendre pour optimiser le temps de traitement de votre code.

Les complexités à connaitre

O(n) : Complexité linéaire

La notation O(n) indique qu’un algorithme a une complexité proportionnelle à la taille de l’entrée.

Autrement dit, le temps d’exécution ne croît pas plus vite qu’une fonction linéaire de la taille de l’entrée n.

Un parcours d’une liste de n éléments nécessite souvent O(n) opérations.

function display(arr) {
    for (const el of arr) {
        console.log(el);
    }
}

Ici, chaque élément est parcouru une seule fois.

Donc si la liste contient 10 éléments, 10 opérations sont effectuées, et si elle en contient 1000, alors 1000 opérations seront effectuées.

Le temps d'exécution croît donc linéairement avec n.

O(n²) : Complexité quadratique

La notation O(n²) indique qu’un algorithme a une complexité proportionnelle au carré de la taille de l’entrée.

Cela signifie que si la taille de l’entrée double, le nombre d’opérations effectuées est multiplié par quatre.

Un algorithme utilisant deux boucles imbriquées est généralement en O(n²).

function compareElements(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

Ici, chaque élément est comparé à tous les autres.

Si la liste contient 10 éléments, 100 itérations sont effectuées, mais avec 1 000 éléments, 1 000 000 de itérations ont lieu.

La croissance quadratique est donc plus gourmande en performances qu’une croissance linéaire.

Les algorithmes de tri par sélection ou par insertion, par exemple, ont une complexité O(n²) dans le pire des cas, ce qui les rend inefficaces pour de très grandes entrées.

O(log(n)) : Complexité logarithmique

La notation O(log(n)) signifie que le temps d’exécution croît proportionnellement au logarithme de la taille de l’entrée.

Cela signifie que si n augmente de manière exponentielle, le temps d’exécution n’augmente que de manière linéaire.

Un exemple classique d’algorithme en O(log(n)) est la recherche dichotomique (ou recherche binaire), utilisée pour rechercher un élément dans une liste triée.

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        let middle = Math.floor((left + right) / 2);

        if (arr[middle] === target) {
            return middle;
        } else if (arr[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

Dans cet algorithme, au lieu de parcourir tous les éléments un par un, on divise la liste en deux à chaque itération. Ainsi, pour une liste de 1 000 éléments, au lieu de faire 1 000 itérations, on en fait seulement environ log₂(1 000) ≈ 10.

Cette optimisation est extrêmement efficace pour de grandes valeurs de n.

Ignorer les constantes

Lorsque l’on parle de complexité algorithmique, on admet que O(2n) = O(n).

Mais pourquoi est-ce que l’on ignore les constantes multiplicatives ?

La notation O(n) représente une limite supérieure (borne asymptotique) jusqu'à une constante. Et mathématiquement, O(2n) = O(n) car il existe une constante c telle que 2n ≤ c * n pour tout n suffisamment grand.

Donc O(2n), O(100n) ou O(0.5n) sont toutes équivalentes à O(n) dans la notation asymptotique.

Conclusion

O(n) est une notation pour comprendre rapidement la complexité d’un algorithme, ce qui va fortement influencer ses performances en fonction du nombre d’éléments n.

• O(n) signifie que l’algorithme a une complexité linéaire.
• O(n²) indique que le temps d’exécution croît de manière quadratique avec la taille de l’entrée, ce qui peut devenir rapidement inefficace pour de grandes valeurs de n.
• O(log(n)) est une complexité logarithmique, ce qui est extrêmement efficace pour des grandes entrées car le nombre d’opérations croît très lentement.