Qu’est-ce que la notation Big-O?

Hibou Gourou

Vous êtes-vous déjà demandé pourquoi un programme que vous avez écrit mettait si longtemps à s'exécuter? Vous aimeriez peut-être savoir si vous pouvez rendre votre code plus efficace. Comprendre comment le code s'exécute peut amener votre code au niveau suivant. La notation Big-O est un outil pratique pour calculer l'efficacité réelle de votre code.

Qu'est-ce que la notation Big-O?

La notation Big-O vous permet de calculer le temps qu'il faudra pour exécuter votre code. Vous pouvez chronométrer physiquement le temps d'exécution de votre code, mais avec cette méthode, il est difficile de détecter de petites différences de temps. Par exemple, le temps qu'il faut entre l'exécution de 20 et 50 lignes de code est très petit. Cependant, dans un grand programme, ces inefficacités peuvent s'additionner.

La notation Big-O compte le nombre d'étapes qu'un algorithme doit exécuter pour évaluer son efficacité. Aborder votre code de cette manière peut être très efficace si vous devez régler votre code pour augmenter son efficacité. La notation Big-O vous permettra de mesurer différents algorithmes par le nombre d'étapes nécessaires pour s'exécuter et de comparer objectivement l'efficacité des algorithmes.

Comment calculer la notation Big-O

Considérons deux fonctions qui comptent le nombre de chaussettes individuelles dans un tiroir. Chaque fonction prend le nombre de paires de chaussettes et renvoie le nombre de chaussettes individuelles. Le code est écrit en Python, mais cela n'affecte pas la façon dont nous comptons le nombre d'étapes.

Algorithme 1:

 def sockCounter(numberOfPairs):
 individualSocks = 0
 for x in range(numberOfPairs):
 individualSocks = individualSocks + 2
 return individualSocks

Algorithme 2:

 def sockCounter(numberOfPairs):
 return numberOfPairs * 2

Ceci est un exemple idiot, et vous devriez être capable de dire facilement quel algorithme est le plus efficace. Mais pour la pratique, passons en revue chacun.

CONNEXION: Qu'est-ce qu'une fonction dans la programmation?

L'algorithme 1 comporte plusieurs étapes:

  1. Il attribue une valeur de zéro à la variable individualSocks.
  2. Il attribue une valeur de un à la variable i.
  3. Il compare la valeur de i à numberOfPairs.
  4. Il ajoute deux aux chaussettes individuelles.
  5. Il s'attribue la valeur accrue de individualSocks à lui-même.
  6. Il incrémente i de un.
  7. Il revient ensuite sur les étapes 3 à 6 le même nombre de fois que (indiviualSocks – 1).

Le nombre d'étapes à effectuer pour l'algorithme 1 peut être exprimé comme suit:

 4n + 2

Il y a quatre étapes que nous devons effectuer n fois. Dans ce cas, n serait égal à la valeur de numberOfPairs. Il y a également 2 étapes qui sont exécutées une fois.

En comparaison, l'algorithme 2 n'a qu'une étape. La valeur de numberOfPairs est multipliée par deux. Nous exprimerions cela comme:

 1

Si ce n'était pas déjà apparent, nous pouvons maintenant facilement voir que l'algorithme 2 est un peu plus efficace.

Analyse Big-O

Généralement, lorsque vous vous intéressez à la notation Big-O d'un algorithme, vous vous intéressez plus à l'efficacité globale et moins à l'analyse fine du nombre d'étapes. Pour simplifier la notation, nous pouvons simplement indiquer l'ampleur de l'efficacité.

Dans les exemples ci-dessus, l'algorithme 2 serait exprimé comme un:

 O(1)

Mais l'algorithme 1 serait simplifié comme suit:

 O(n)

Cet instantané rapide nous indique comment l'efficacité de l'algorithme 1 est liée à la valeur de n. Plus le nombre est élevé, plus l'algorithme devra effectuer d'étapes.

Code linéaire

Comme nous ne connaissons pas la valeur de n, il est plus utile de réfléchir à la façon dont la valeur de n affecte la quantité de code à exécuter. Dans l'algorithme 1, nous pouvons dire que la relation est linéaire. Si vous tracez le nombre de pas par rapport à la valeur de n, vous obtenez une ligne droite qui monte.

Code quadratique

Toutes les relations ne sont pas aussi simples que l'exemple linéaire. Imaginez que vous disposez d'un tableau 2D et que vous souhaitez rechercher une valeur dans le tableau. Vous pouvez créer un algorithme comme celui-ci:

 def searchForValue(targetValue, arraySearched):
 foundTarget = False
 for x in arraySearched:
 for y in x:
 if(y == targetValue):
 foundTarget = True
 return foundTarget

Dans cet exemple, le nombre d'étapes dépend du nombre de tableaux dans arraySearched et du nombre de valeurs dans chaque tableau. Ainsi, le nombre d'étapes simplifié serait n * n ou n².

Cette relation est une relation quadratique, ce qui signifie que le nombre d'étapes dans notre algorithme augmente de façon exponentielle avec n. En notation Big-O, vous l'écririez comme suit:

 O(n²)

CONNEXION: Outils utiles pour vérifier, nettoyer et optimiser les fichiers CSS

Code logarithmique

Bien qu'il existe de nombreuses autres relations, la dernière relation que nous examinerons est celle des relations logarithmiques. Pour rafraîchir votre mémoire, le log d'un nombre est la valeur d'exposant nécessaire pour atteindre un nombre donné une base. Par exemple:

 log 2 (8) = 3

Le log est égal à trois car si notre base était de 2, nous aurions besoin d'une valeur d'exposant de 3 pour obtenir le nombre 8.

Ainsi, la relation d'une fonction logarithmique est l'opposé d'une relation exponentielle. Lorsque n augmente, moins de nouvelles étapes sont nécessaires pour exécuter l'algorithme.

À première vue, cela semble contre-intuitif. Comment les étapes d'un algorithme peuvent-elles croître plus lentement que n? Les recherches binaires en sont un bon exemple. Considérons un algorithme pour rechercher un nombre dans un tableau de valeurs uniques.

  • Nous commencerons par un tableau à rechercher dans l'ordre du plus petit au plus grand.
  • Ensuite, nous vérifierons la valeur au milieu du tableau.
  • Si votre nombre est supérieur, nous exclurons les nombres inférieurs de notre recherche et si le nombre était inférieur, nous exclurons les nombres supérieurs.
  • Maintenant, nous allons regarder le nombre du milieu des nombres restants.
  • Encore une fois, nous exclurons la moitié des nombres selon que notre valeur cible est supérieure ou inférieure à la valeur moyenne.
  • Nous continuerons ce processus jusqu'à ce que nous trouvions notre cible ou que nous déterminions qu'elle ne figure pas dans la liste.

Comme vous pouvez le voir, étant donné que les recherches binaires éliminent la moitié des valeurs possibles à chaque passage, à mesure que n augmente, l'effet sur le nombre de fois que nous vérifions le tableau est à peine affecté. Pour exprimer cela en notation Big-O, nous écririons:

 O(log(n))

L'importance de la notation Big-O

Big-O nation vous offre un moyen rapide et facile de communiquer l'efficacité d'un algorithme. Cela facilite le choix entre différents algorithmes. Cela peut être particulièrement utile si vous utilisez un algorithme d'une bibliothèque et que vous ne savez pas nécessairement à quoi ressemble le code.

Lorsque vous apprenez à coder pour la première fois, vous commencez par des fonctions linéaires. Comme vous pouvez le voir sur le graphique ci-dessus, cela vous mènera très loin. Mais à mesure que vous devenez plus expérimenté et que vous commencez à créer un code plus complexe, l'efficacité commence à devenir un problème. Une compréhension de la façon de quantifier l'efficacité de votre code vous donnera les outils dont vous avez besoin pour commencer à le régler pour plus d'efficacité et à peser les avantages et les inconvénients des algorithmes.