Introduction à la notation Big O

Introduction

Dans la leçon précédente, nous avons appris à évaluer l'efficacité d'un algorithme en comptant ses opérations élémentaires. Cela nous a permis d'obtenir une fonction de coût précise, comme $C(n)=2n^2+2$, qui décrit le nombre exact d'opérations en fonction de la taille des données n.

Cependant, comme nous l'avons évoqué, ces formules exactes peuvent être complexes à calculer et contiennent des détails qui, en pratique, sont peu importants. Est-ce que le "+2" dans $2n^2+2$ a un réel impact lorsque n devient très grand ? La réponse est non. Ce qui compte vraiment, c'est la manière dont le temps d'exécution augmente lorsque la taille des données explose.

L'objectif de cette leçon est de vous apprendre à utiliser la notation Big O (grand O). C'est l'outil standard utilisé par tous les développeurs pour décrire et comparer la croissance du temps d'exécution des algorithmes. Maîtriser cette notation est fondamental pour atteindre votre but : écrire du "code clean" et, surtout, performant.

1. De la fonction de coût à la notation Big O

Imaginez que l'analyse d'un algorithme nous donne la fonction de coût suivante :
$C(n)=2n^2+5n+10$

Quand n est petit, disons n=10, chaque terme a son importance :

• $2n^2=2\times 100=200$
• $5n=5\times 10=50$
• $10$

Le coût total est de 260.

Maintenant, que se passe-t-il si n est grand, disons n=1 000 000 ?

• $2n^2=2\times (10^6{)}^2=2\times 10^{12}$ (deux mille milliards)
• $5n=5\times 10^6$ (cinq millions)
• $10$

Le terme $2n^2$ est si énorme qu'il rend les autres termes (5n et 10) complètement négligeables. L'essentiel de la performance de l'algorithme est dicté par son terme qui croît le plus vite.

La notation Big O est une manière de formaliser cette idée en se concentrant sur l'ordre de grandeur de la croissance pour de grandes valeurs de n. On parle de complexité asymptotique.

Pour trouver la notation Big O à partir d'une fonction de coût, on applique deux règles simples :

1. Garder uniquement le terme dominant : C'est le terme qui croît le plus rapidement. Dans $2n^2+5n+10$, le terme dominant est $2n^2$.
2. Supprimer les constantes multiplicatives : Le facteur 2 dans $2n^2$ dépend souvent de la machine ou de détails d'implémentation. Ce qui nous intéresse, c'est la nature de la croissance, ici en $n^2$. On le supprime donc.

Ainsi, la fonction de coût $C(n)=2n^2+5n+10$ se simplifie en $O(n^2)$. On lit "complexité en O de n au carré".

2. Comprendre les ordres de grandeur avec une histoire

Pour vous familiariser avec différentes "familles" de complexité, rien de tel qu'une petite histoire. Je vous invite à lire le texte suivant qui, à travers une analogie avec des cadenas, illustre brillamment comment des approches différentes peuvent avoir des performances radicalement opposées.

Ce que cette histoire nous apprend :

• La méthode "brute-force" (tester toutes les combinaisons) est de complexité exponentielle, $O(10^n)$. Ajouter un seul chiffre au cadenas multiplie le temps par 10. C'est une très mauvaise stratégie, qui devient très vite irréalisable.
• La méthode "intelligente" de Bill (trouver les chiffres un par un) est de complexité linéaire, $O(n)$. Si on double le nombre de chiffres, on double approximativement le temps. C'est beaucoup plus raisonnable.
• La méthode "radicale" de Jack (casser le cadenas) est de complexité constante, $O(1)$. Le temps nécessaire ne dépend absolument pas du nombre de chiffres. C'est l'idéal en termes d'efficacité.

L'article mentionne aussi la complexité spatiale, qui mesure l'espace mémoire utilisé par un algorithme. C'est un concept similaire, mais pour le reste de ce module, nous nous concentrerons sur la complexité temporelle (le temps d'exécution).

3. Les grandes familles de complexité

Maintenant que vous avez une intuition, systématisons les choses. Il existe plusieurs grandes "classes" de complexité Big O. Nous allons les passer en revue, de la plus efficace à la moins efficace.

L'article ci-dessous détaille chacune de ces complexités. Nous allons résumer les points clés, mais n'hésitez pas à le consulter pour plus de détails et des exemples concrets.

Voici un résumé des complexités les plus courantes, avec des exemples en pseudo-code.

Pour visualiser à quel point ces croissances sont différentes, regardez le graphique suivant. Il montre clairement pourquoi on préfère un algorithme en $O(\log n)$ à un algorithme en $O(n^2)$ quand on traite beaucoup de données.

4. Application pratique

Revenons à l'exercice de l'article d'OpenClassrooms pour consolider notre compréhension. Il analyse trois algorithmes.

Analysons rapidement les solutions :

• Algorithme déplacement : Il ne contient aucune boucle qui dépende de la taille d'une donnée d'entrée n. Il exécute juste une série de conditions. Son temps d'exécution est donc constant. Complexité : $O(1)$.

• Algorithme ramasser : Il contient une boucle Tant Que. Dans le pire des cas, cette boucle s'exécute max_déplacement fois, qui est défini comme 30n. Le coût est donc proportionnel à n. En appliquant nos règles, on ignore la constante 30. Complexité : $O(n)$.

• Algorithme tri : Il contient deux boucles Pour imbriquées, chacune allant jusqu'à taille - 1 (que l'on note n). Le corps de la boucle interne est donc exécuté environ $n\times n=n^2$ fois. Complexité : $O(n^2)$.

C'est exactement ce que nous avons appris à faire dans la leçon précédente, mais maintenant nous avons un langage simple et standardisé pour exprimer le résultat !

Conclusion

Félicitations ! Vous venez d'acquérir l'un des outils les plus importants de l'arsenal d'un programmeur.

Points clés à retenir :

• La notation Big O décrit la croissance du temps d'exécution d'un algorithme lorsque la taille des données (n) augmente.
• Elle nous permet de nous concentrer sur l'essentiel en ignorant les constantes et les termes de plus bas niveau. On passe de $C(n)=2n^2+5n+10$ à $O(n^2)$.
• Il existe une hiérarchie de complexités, des plus efficaces (vertes) aux moins efficaces (rouges) : $O(1)$ < $O(\log n)$ < $O(n)$ < $O(n\log n)$ < $O(n^2)$ < $O(2^n)$ < $O(n!)$.
• Connaître la complexité Big O d'un algorithme nous aide à prédire sa performance et à choisir la meilleure solution pour un problème donné.

Et après ?

Maintenant que vous comprenez le langage de la complexité, nous allons l'appliquer. Dans la prochaine leçon, nous allons analyser et classer les algorithmes que nous avons déjà étudiés ou que nous allons bientôt étudier (comme la recherche linéaire, la recherche dichotomique et les tris simples) en utilisant leur notation Big O. Cela rendra leurs différences de performance concrètes et vous aidera à comprendre pourquoi on choisit un algorithme plutôt qu'un autre.