Notation Big-O en français

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

La notation Big-O est une méthode utilisée pour évaluer la complexité algorithmique d'une fonction ou d'un algorithme dans le cas le plus défavorable. Elle permet d'analyser le temps ou l'espace mémoire maximal nécessaire pour résoudre un problème spécifique. Grâce à Big-O, il est possible de refactoriser ou de réécrire des solutions pour atteindre une meilleure efficacité en termes de temps et d'espace.

Les temps d'exécution courants

Voici quelques exemples de temps d'exécution typiques :

| Complexité | Nom | Description | Cas d'utilisation | |-----------------|-----------------------------|-------------------------------------------------------|-----------------------------------------------------| | O(1) | Temps constant | Le temps requis reste le même, peu importe la taille de l'entrée. | Accéder à un élément dans un tableau. | | O(log(n)) | Temps logarithmique | Le temps est une fonction logarithmique de la taille de l'entrée n. | Analyser l'algorithme de recherche binaire. | | O(n) | Temps linéaire | Le temps requis est proportionnel à la taille de l'entrée n. | Parcourir un tableau de taille n. | | O(n^2) | Temps polynomial/quadratique | Le temps requis est calculé en multipliant la taille d'entrée n par elle-même. | L'algorithme de tri à bulles a une complexité quadratique. | | O(2^n) | Temps exponentiel | Le temps requis double pour chaque nouvel élément ajouté. | La série de Fibonacci. | | O(n!) | Temps factoriel | Le temps requis est équivalent au factoriel de la taille d'entrée. | Le problème du voyageur de commerce.

Simplification des expressions Big-O

Lors de l'identification d'une expression qui caractérise la complexité d'un algorithme, il est courant d'avoir plusieurs termes (par exemple, O(n) + O(log(n))). En termes de Big-O, l'accent est mis sur le changement relatif lorsque la taille de l'entrée augmente. À mesure que l'entrée devient plus grande (tend vers l'infini), les termes de plus haut ordre prévalent sur les termes de plus bas ordre, ce qui explique pourquoi la notation Big-O se simplifie souvent à O(n).

Exemple en Python avec Big-O

Voici un exemple en Python qui analyse la complexité en temps et en espace de la fonction foo():

def foo(list1, list2):  
    for item in list1:  
        print(f"Boucle extérieure : {item}")  
        for item2 in list2:  
            print(f"Boucle intérieure : {item2}")

foo(["Bonjour", "Monde"], ["Spam", "Œufs"])

La boucle intérieure a une complexité équivalente à O(n), et la boucle extérieure exécutera la boucle intérieure n fois. Par conséquent, la notation Big-O pour la fonction foo() serait n * O(n) = O(n²).