Complexité algorithmique

En clair. Big-O, cas pire

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Complexité algorithmique », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

Définitions clés

• Complexité en temps : estimation du nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n de l'entrée, indépendamment de la machine.
• Complexité en espace : mémoire supplémentaire utilisée.
• Notation de Landau O(·) : f(n) = O(g(n)) s'il existe c et n₀ tels que f(n) ≤ c·g(n) pour n ≥ n₀. On ne garde que le terme dominant, sans les constantes.

On distingue meilleur cas, cas moyen et pire cas ; on raisonne par défaut sur le pire cas, seule garantie fiable.

Les classes usuelles

Ordre de croissance : $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$.

Déterminer la complexité d'un code

1. instructions successives → on additionne puis on garde le maximum ;
2. boucles imbriquées → on multiplie les nombres d'itérations ;
3. variable divisée par 2 à chaque tour → log₂ n itérations.

def maximum(t):          # n-1 comparaisons -> O(n)
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

def doublons(t):         # boucles imbriquées -> O(n^2)
    for i in range(len(t)):
        for j in range(i+1, len(t)):
            if t[i] == t[j]:
                return True
    return False

Étude de cas : séquentielle contre dichotomie

• Recherche séquentielle : jusqu'à n comparaisons → O(n).
• Recherche dichotomique (tableau trié) : l'espace est divisé par 2 à chaque étape, d'où k comparaisons avec 2ᵏ ≥ n, soit k = ⌈log₂ n⌉ → O(log n).

Exemple chiffré : pour n = 1 000 000, la dichotomie ne demande que 20 comparaisons contre un million. Sur une machine à 10⁸ opérations/s, un algorithme O(n²) avec n = 10⁵ prend ≈ 100 s, contre 0,017 s pour un O(n log n).

Terminaison et correction

• Terminaison : on exhibe un variant de boucle, entier positif strictement décroissant.
• Correction : on exhibe un invariant de boucle, propriété vraie à chaque itération, qui donne le résultat en sortie.

Pour le tri par sélection, l'invariant est : « après l'itération i, les i premières cases contiennent les i plus petits éléments, triés ».

Compromis temps / espace

La mémoïsation de Fibonacci fait passer une complexité O(2ⁿ) à O(n) au prix d'un tableau de taille n : c'est le principe de la programmation dynamique.

Erreurs fréquentes

• ❌ Écrire O(3n² + 5n) : on écrit O(n²).
• ❌ Confondre nombre d'itérations et nombre d'opérations par itération.
• ❌ Penser qu'un O(log n) est toujours plus rapide : pour de petits n, les constantes dominent.
• ❌ Oublier que la dichotomie exige un tableau trié (et que trier coûte O(n log n)).

Quiz de révision

1. Complexité du tri par insertion dans le pire cas ? → O(n²).
2. Combien de comparaisons pour une dichotomie sur 1024 éléments ? → 10.
3. Que garantit un variant de boucle ? → La terminaison.
4. Intérêt de la mémoïsation ? → Échanger de l'espace mémoire contre du temps de calcul.