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

Vous êtes-vous déjà demandé pourquoi un programme que vous aviez é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 donne un moyen de calculer le temps qu'il faudra pour exécuter votre code. Vous pouvez physiquement chronométrer 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 nécessaire 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 avez besoin d'ajuster 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
pour x dans la plage (numberOfPairs):
CHAUSSETTES INDIVIDUELLES = CHAUSSETTES INDIVIDUELLES + 2
retour individuel

Algorithme 2:

def sockCounter (numberOfPairs):
retourne numberOfPairs * 2

C'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 d'eux.

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

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

Si vous apprenez à programmer votre propre code, vous devrez comprendre ce que sont les fonctions.

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 en 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 aux é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:

Sur)

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 manière 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 d'étapes vs. 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 avez 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 = Faux
pour x dans le tableau
pour y en x:
if (y == targetValue):
foundTarget = Vrai
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 croît exponentiellement avec n. En notation Big-O, vous l'écririez comme suit:

O (n²)

EN RELATION: 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. À mesure que 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 allons commencer 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 plus élevé, nous exclurons les nombres inférieurs dans notre recherche et si le nombre était inférieur, nous exclurons les nombres plus élevés.
• 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, puisque les recherches binaires éliminent la moitié des valeurs possibles à chaque passage, au fur et à 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.

10 erreurs de programmation et de codage les plus courantes

Les erreurs de codage peuvent entraîner de nombreux problèmes. Ces conseils vous aideront à éviter les erreurs de programmation et à garder votre code significatif.

A propos de l'auteur