Notation Big O: Explication avec des exemples

[Anonymous]

Je préférerais une définition aussi peu formelle que possible et des mathématiques simples.

[Isaac]

La notation Big O est une représentation relative de la complexité d’un algorithme.

Il y a des mots importants choisis dans cette phrase :

• relative: on ne peut comparer que des pommes avec des pommes. Vous ne pouvez pas comparer un algorithme qui effectue une multiplication arithmétique à un algorithme qui trie une liste d’entiers. Mais la comparaison de deux algorithmes effectuant des opérations arithmétiques (une multiplication, une addition) vous apprendra quelque chose de significatif ;

• représentation: BigO (dans sa forme la plus simple) réduit la comparaison entre les algorithmes à une seule variable. Cette variable est choisie sur la base d’observations ou d’hypothèses. Par exemple, les algorithmes de tri sont généralement comparés sur la base d’opérations de comparaison (comparaison de deux nœuds pour déterminer leur ordre relatif). Cela suppose que la comparaison est coûteuse. Mais que se passe-t-il si la comparaison est bon marché mais que la permutation est coûteuse ? Cela modifie la comparaison ; et

• complexité : s’il me faut une seconde pour trier 10 000 éléments, combien de temps me faudra-t-il pour en trier un million ? Dans ce cas, la complexité est une mesure relative à quelque chose d’autre.

Le meilleur exemple de BigO auquel je pense est l’arithmétique. Prenons deux nombres (2468 et 1357). Les opérations arithmétiques de base que nous avons apprises à l’école sont les suivantes :

• l’addition ;
• la soustraction ;
• la multiplication ; et
• la division.

Chacune de ces opérations est une opération ou un problème. Une méthode pour les résoudre s’appelle un algorithme.

L’addition est la plus simple. Vous alignez les nombres (vers la droite) et vous additionnez les chiffres dans une colonne en inscrivant le dernier chiffre de cette addition dans le résultat. La partie « dizaines » de ce nombre est reportée dans la colonne suivante.

Supposons que l’addition de ces nombres soit l’opération la plus coûteuse de cet algorithme. Il est logique que pour additionner ces deux nombres, nous devions additionner 4 chiffres (et éventuellement en reporter un cinquième). Si nous additionnons deux nombres de 100 chiffres, nous devons effectuer 100 additions. Si nous ajoutons deux nombres à 10 000 chiffres, nous devons effectuer 10 000 additions.

Vous avez vu le schéma ? La complexité (c’est-à-dire le nombre d’opérations) est directement proportionnelle au nombre de chiffres n du plus grand nombre. Nous appelons cela O(n) ou complexité linéaire.

La soustraction est similaire (sauf qu’il peut être nécessaire d’emprunter au lieu de reporter).

La multiplication est différente. On aligne les nombres, on prend le premier chiffre du nombre inférieur et on le multiplie à son tour par chaque chiffre du nombre supérieur et ainsi de suite pour chaque chiffre. Ainsi, pour multiplier nos deux nombres à 4 chiffres, nous devons effectuer 16 multiplications. Il se peut que nous ayons besoin d’effectuer 10 ou 11 additions en colonne pour obtenir le résultat final.

Si nous avons deux nombres à 100 chiffres, nous devons effectuer 10 000 multiplications et 200 additions. Pour deux nombres d’un million de chiffres, nous devons effectuer un trillion (10¹²) de multiplications et deux millions d’additions.

Comme l’algorithme augmente avec n-au carré, il s’agit de O(n²) ou complexité quadratique. C’est le bon moment pour introduire un autre concept important :

Nous ne nous intéressons qu’à la partie la plus significative de la complexité.

Les personnes avisées auront peut-être compris que nous pourrions exprimer le nombre d’opérations sous la forme suivante : n² + 2n. Mais comme vous l’avez vu dans notre exemple avec deux nombres d’un million de chiffres chacun, le deuxième terme (2n) devient insignifiant (représentant 0,0002% du total des opérations à ce stade).

On peut remarquer que nous avons supposé le pire scénario ici. Lors de la multiplication de nombres à 4 chiffres, si l’un d’entre eux a 4 chiffres et l’autre 5 chiffres, nous n’avons que 20 multiplications. Cependant, nous calculons le pire scénario pour ce « n », c’est-à-dire lorsque les deux sont des nombres à 4 chiffres. La notation Big O concerne donc le pire scénario d’un algorithme.

[Michel]

La notation Big O montre comment un algorithme s’adapte à la taille de l’entrée.

O(n²) : connu sous le nom de complexité quadratique

• 1 élément : 1 opération
• 10 éléments : 100 opérations
• 100 éléments : 10 000 opérations

Remarquez que le nombre d’éléments augmente avec un facteur de 10, mais que le temps augmente avec un facteur de 10². En fait, n=10 et donc O(n²) nous donne le facteur d’échelle n² qui est 10².

O(n) : connu sous le nom de complexité linéaire

• 1 élément : 1 opération
• 10 éléments : 10 opérations
• 100 éléments : 100 opérations

Cette fois, le nombre d’éléments augmente d’un facteur de 10, tout comme le temps. n=10 et le facteur d’échelle de O(n) est donc de 10.

O(1) : connu sous le nom de complexité constante

• 1 élément : 1 opération
• 10 éléments : 1 opération * 10 éléments : 1 opération * 100 éléments : 1 opération
• 100 éléments : 1 opération

Le nombre d’éléments augmente toujours d’un facteur de 10, mais le facteur d’échelle O(1) est toujours de 1.

O(log n) : connu sous le nom de complexité logarithmique

• 1 élément : 1 opération
• 10 éléments : 2 opérations
• 100 éléments : 3 opérations
• 1000 éléments : 4 opérations
• 10 000 éléments : 5 opérations

Le nombre de calculs n’est augmenté que par le logarithme de la valeur d’entrée. Ainsi, dans ce cas, en supposant que chaque calcul prenne 1 seconde, le logarithme de la valeur d’entrée n est le temps nécessaire, d’où log n.

C’est l’essentiel. Ils réduisent les mathématiques de sorte que ce n’est peut-être pas exactement n² ou quoi que ce soit qu’ils disent, mais ce sera le facteur dominant dans la mise à l’échelle.

[Henri]

En une phrase : Lorsque la taille de votre travail augmente, combien de temps faut-il pour l’accomplir ?

Il est évident que l’on utilise uniquement la « taille » comme entrée et le « temps nécessaire » comme sortie - la même idée s’applique si l’on veut parler de l’utilisation de la mémoire, etc.

Voici un exemple où nous avons N t-shirts que nous voulons faire sécher. Nous supposerons qu’il est incroyablement rapide de les mettre en position de séchage (c’est-à-dire que l’interaction humaine est négligeable).

• Utilisation d’un fil à linge à l’extérieur : en supposant que vous disposiez d’un jardin infiniment grand, le linge sèche en O(1) temps. Quelle que soit la quantité de linge, il bénéficiera du même soleil et de la même quantité d’air frais, de sorte que la taille n’affecte pas le temps de séchage.

• En utilisant un sèche-linge : vous insérez 10 chemises dans chaque charge, et elles sont prêtes une heure plus tard. (Le séchage de 50 chemises prend donc environ 5 fois plus de temps que le séchage de 10 chemises.

• Tout insérer dans un armoire lingère : Si nous insérons tout dans une grande pile et laissons la chaleur générale agir, il faudra beaucoup de temps pour que les chemises du milieu sèchent. Je ne voudrais pas deviner les détails, mais je pense que c’est au moins O(n²) - plus on augmente la charge de lavage, plus le temps de séchage augmente rapidement.

[Jacques]

La notation Big O est le plus souvent utilisée par les programmeurs comme une mesure approximative de la durée d’un calcul (algorithme) exprimée en fonction de la taille de l’ensemble des données d’entrée.

La notation Big O est utile pour comparer la capacité de deux algorithmes à s’adapter à l’augmentation du nombre d’entrées.

Plus précisément, la notation Big O est utilisée pour exprimer le comportement asymptotique d’une fonction. Cela signifie que la fonction se comporte lorsqu’elle s’approche de l’infini.

Dans de nombreux cas, le « O » d’un algorithme correspond à l’un des cas suivants :

• O(1) - Le temps d’exécution est le même quelle que soit la taille de l’ensemble d’entrée. Un exemple est l’accès à un élément de tableau par index.

• O(Log N) - Le temps d’exécution augmente à peu près en fonction du log2(n). Par exemple, 1024 éléments prennent environ deux fois plus de temps que 32 éléments, car Log2(1024) = 10 et Log2(32) = 5. Un exemple est la recherche d’un élément dans un arbre de recherche binaire (BST).

• O(N) - Temps d’exécution qui augmente linéairement avec la taille de l’ensemble d’entrée. En d’autres termes, si vous doublez le nombre d’éléments dans l’ensemble d’entrée, l’algorithme prend environ deux fois plus de temps. Un exemple est de compter le nombre d’éléments dans une liste chaînée.

• O(N Log N) - Le temps d’exécution augmente en fonction du nombre d’éléments multiplié par le résultat de Log2(N). Les tris en tas et les tris rapides sont des exemples de cette approche.

• O(N²) - Le temps de traitement est à peu près égal au carré du nombre d’éléments. Le tri à bulles est un exemple de cette approche.

• O(N !) - Le temps de traitement est égal à la factorielle de l’ensemble des données d’entrée. La solution du problème du voyageur de commerce en force brute est un exemple de cette approche.

Big O ignore les facteurs qui ne contribuent pas de manière significative à la courbe de croissance d’une fonction lorsque la taille de l’entrée augmente vers l’infini. Cela signifie que les constantes qui sont ajoutées ou multipliées par la fonction sont simplement ignorées.