Notation Big-O : Comprendre et Mesurer l'Efficacité de Vos Algorithmes

Vous vous êtes déjà demandé pourquoi un programme que vous avez développé mettait tant de temps à s'exécuter ? Apprenez à optimiser votre code grâce à la notation Big-O, un outil essentiel pour évaluer sa performance réelle et l'améliorer significativement.

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

La notation Big-O permet d'évaluer le temps d'exécution d'un algorithme en comptant le nombre d'opérations élémentaires nécessaires. Contrairement au chronométrage réel, qui est imprécis pour de petites variations, elle révèle les inefficacités qui s'accumulent dans les grands programmes.

Elle mesure l'efficacité en termes d'étapes algorithmiques, facilitant la comparaison objective entre algorithmes et l'optimisation de votre code.

Comment calculer la notation Big-O ?

Considérons deux fonctions Python comptant le nombre de chaussettes individuelles à partir du nombre de paires. Le langage n'impacte pas le comptage des étapes.

Algorithme 1 :

def sock_counter(number_of_pairs):
    individual_socks = 0
    for x in range(number_of_pairs):
        individual_socks += 2
    return individual_socks

Algorithme 2 :

def sock_counter(number_of_pairs):
    return number_of_pairs * 2

Cet exemple simple montre qu'il est évident que l'algorithme 2 est plus efficace. Examinons les étapes en détail.

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

L'algorithme 1 nécessite :

1. Initialisation de individual_socks à 0.
2. Initialisation du compteur de boucle.
3. Comparaison i < number_of_pairs.
4. Addition de 2 à individual_socks.
5. Mise à jour de la variable.
6. Incrémentation du compteur.
7. Répétition des étapes 3-6 pour n-1 fois (où n = number_of_pairs).

Nombre total d'étapes : 4n + 2 (4 étapes par itération × n + 2 étapes fixes).

4n + 2

L'algorithme 2 ne requiert qu'1 étape : une multiplication.

1

Analyse Big-O

En pratique, on simplifie en ne retenant que le terme dominant pour décrire la complexité asymptotique.

Algorithme 2 : O(1) (constante).

O(1)

Algorithme 1 : O(n) (linéaire).

O(n)

Code linéaire

La performance croît proportionnellement à n, formant une droite.

Code quadratique

Pour une recherche dans un tableau 2D :

def search_for_value(target_value, searched_array):
    found = False
    for x in searched_array:
        for y in x:
            if y == target_value:
                found = True
                break
    return found

Étapes : n × n = n², complexité O(n²).

O(n²)

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

Code logarithmique

Exemple : log₂(8) = 3, car 2³ = 8.

log₂(8) = 3

Dans une recherche binaire triée :

• Vérifiez le milieu.
• Éliminez la moitié inadéquate.
• Répétez jusqu'à trouver ou conclure l'absence.

Complexité : O(log n), car chaque étape divise l'espace de recherche par 2.

O(log n)

L'importance de la notation Big-O

La notation Big-O communique rapidement l'efficacité d'un algorithme, aidant à choisir entre options, y compris celles de bibliothèques tierces. Pour les débutants, O(n) suffit souvent ; pour les projets complexes, maîtriser les complexités supérieures est crucial pour scaler efficacement.