Vous êtes-vous déjà demandé pourquoi un programme que vous avez écrit prenait si longtemps à s'exécuter ? Peut-être aimeriez-vous savoir si vous pouvez rendre votre code plus efficace. Comprendre comment le code s'exécute peut amener votre code au niveau supérieur. La notation Big-O est un outil pratique pour calculer l'efficacité réelle de votre code.
La notation Big-O vous donne un moyen de calculer combien de temps 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 qu'il faut entre l'exécution de 20 et 50 lignes de code est très faible. 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é. Approcher votre code de cette manière peut être très efficace si vous avez besoin d'ajuster votre code pour augmenter l'efficacité. La notation Big-O vous permettra de mesurer différents algorithmes par le nombre d'étapes dont ils ont besoin pour s'exécuter et de comparer objectivement l'efficacité des algorithmes.
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) :
chaussettes individuelles =0
pour x dans la plage (numberOfPairs):
chaussettes individuelles =chaussettes individuelles + 2
retourner des chaussettes individuelles Algorithme 2 :
def sockCounter(numberOfPairs) :
renvoyer nombreDePaires * 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.
EN RELATION :Qu'est-ce qu'une fonction en programmation ?
L'algorithme 1 comporte plusieurs étapes :
Le nombre d'étapes que nous devons accomplir pour l'algorithme un peut être exprimé comme :
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 aussi 2 étapes qui sont complétées une fois.
En comparaison, l'algorithme 2 ne comporte qu'une seule étape. La valeur de numberOfPairs est multipliée par deux. Nous exprimerions cela comme :
1 Si ce n'était pas déjà évident, nous pouvons maintenant facilement voir que l'algorithme 2 est beaucoup plus efficace.
Généralement, lorsque vous vous intéressez à la notation Big-O d'un algorithme, vous vous intéressez davantage à 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 un est liée à la valeur de n. Plus le nombre est élevé, plus l'algorithme devra effectuer d'étapes.
Étant donné que 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 de pas par rapport à la valeur de n, vous obtenez une ligne droite qui monte.
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) :
cible trouvée =Faux
pour x dans le tableauRecherché :
pour y en x :
if(y ==targetValue):
cible trouvée =Vrai
renvoie la cible trouvée 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 simplifié d'étapes serait n * n ou n².
Cette relation est une relation quadratique, ce qui signifie que le nombre d'étapes dans notre algorithme croît de façon exponentielle avec n. En notation Big-O, vous l'écririez ainsi :
O(n²) CONNEXION :Outils utiles pour vérifier, nettoyer et optimiser les fichiers CSS
Bien qu'il existe de nombreuses autres relations, la dernière relation que nous examinerons est la relation logarithmique. Pour vous rafraîchir la mémoire, le log d'un nombre est la valeur d'exposant nécessaire pour atteindre un nombre donné d'une base. Par exemple :
log 2 (8) =3 Le log est égal à trois car si notre base était 2, nous aurions besoin d'une valeur d'exposant de 3 pour arriver au 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.
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 où nous vérifions le tableau est à peine affecté. Pour exprimer cela en notation Big-O, nous écrirons :
O(log(n)) 
Big-O nation vous offre un moyen simple et rapide 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 avec 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 gagnez en expérience et que vous commencez à créer du 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 l'efficacité et à peser le pour et le contre des algorithmes.