Le Big O

La Complexité Algorithmique

En développement, il est crucial de comprendre la complexité algorithmique afin de pouvoir évaluer la performance de son code. Dans cet article, nous allons examiner ce que l'on appelle le "Big O" et comment il peut être utilisé dans nos activités quotidiennes.

Qu'est-ce que le Big O?

Le Big O est un outil utilisé pour mesurer la complexité d'un algorithme. En d'autres termes, c'est une manière de quantifier la performance des algorithmes et de comparer leur efficacité sur 2 aspects.

La complexité temporelle : Le temps qu'il faut pour exécuter un algorithme.
La complexité "spatiale" : L'espace mémoire que prend un algorithme.

Le Big O ne mesure pas la vitesse exacte ou la mémoire utilisée. Au lieu de cela, il utilise une notation permettant de déterminer la croissance du temps de traitement ou de la consommation de mémoire de l'algorithme en fonction du nombre d'élément en entrée de celui-ci. Cette mesure permet de comparer des algorithmes en termes d'efficacité relative.

Cas d'utilisation

Prenons un exemple simple pour illustrer comment le Big O peut être utilisé. Disons que nous avons une fonction qui prend une variable n et boucle sur chacun des éléments :

La complexité temporelle de cette fonction est O(n). Cela signifie que le temps que prend CountSheep(n) pour s'exécuter est proportionnel à la taille de n. Autrement dit, plus n est grand, plus la fonction mettra de temps à s'exécuter.

Il est important de noter, que, si dans cette méthode, nous avions eu 2 boucles à la suite :

Nous n'aurions pas utilisé la notation O(2n), les constantes sont généralement omises pour faciliter la comparaison et rester concentré sur la croissance en fonction de l'entrée.

Concernant la complexité "spatiale" (l'espace mémoire), nous aurions ici O(1), il n'y a pas d'augmentation de la quantité de mémoire en fonction de l'entrée. 

Pour aller plus loin

Je vais faire un focus sur la complexité temporelle, mais le fonctionnement reste le même pour la complexité "spatiale",  mais Quelques notations courantes pour les algorithmes "peu" complexe :

• O(1) : Temps d'exécution constant, indépendamment de la taille de l'entrée.
• O(log n) : Temps d'exécution logarithmique, l'algorithme se divise généralement en deux à chaque étape.
• O(n) : Temps d'exécution linéaire, le temps d'exécution augmente linéairement avec la taille de l'entrée.

Quelques notations courantes pour les algorithmes moyennement complexe ou complexe :

• O(n log n) : Temps d'exécution linéaire logarithmique, souvent présent dans les algorithmes de tri avancés.
• O(n²) : Temps d'exécution quadratique, souvent présent dans les algorithmes de tri simples comme le tri à bulles.
• O(2^n) : Temps d'exécution exponentiel, souvent présent dans les algorithmes de recherche exhaustive.
• O(n!) : Temps d'exécution factoriel, souvent présent dans les problèmes de voyageur de commerce.

Voici 2 exemples de code, pouvez vous trouver leur complexité temporelle.

Exemple 1 :

Solution

O(n^2)

Exemple 2 :

Solution

O(2^n)

En conclusion

Le Big O est un outil puissant pour mesurer la complexité des algorithmes, j'espère que celui-ci vous permettra de prendre les bonnes décisions dans la conception de vos algorithmes.

Ꮚ`ꈊ´Ꮚ

Un petit lien bien utile : https://bigocheatsheet.io/