Complexité algorithmique

🤔 Qu'est-ce que la complexité ?

Deux algorithmes peuvent résoudre le même problème, mais l'un peut être mille fois plus rapide que l'autre sur de grandes données. La complexité algorithmique est l'outil mathématique qui permet de comparer cette efficacité sans avoir à mesurer le temps réel (qui dépend du matériel, du langage, etc.).

On distingue deux types de complexité :

• Complexité temporelle : nombre d'opérations élémentaires en fonction de la taille de l'entrée n.
• Complexité spatiale : quantité de mémoire utilisée. Moins souvent demandée au bac, mais à connaître.

📐 La notation grand O

La notation O(f(n)) (lire "grand O de f de n") décrit le comportement asymptotique de l'algorithme : comment le nombre d'opérations grandit quand n devient très grand.

On dit que T(n) = O(f(n)) si, à partir d'un certain n₀,
T(n) ≤ c × f(n)  pour une constante c > 0.

Autrement dit : f(n) est un majorant du coût, aux constantes près.

Exemples concrets :
T(n) = 3n + 7        →  O(n)       (le 3 et le 7 "disparaissent")
T(n) = 5n² + 2n + 1  →  O(n²)      (le terme dominant gagne)
T(n) = n·log(n) + n  →  O(n log n) (n·log n domine n pour grand n)

📊 Graphique comparatif

Cliquez sur les courbes pour les afficher ou masquer. Passez la souris sur le graphique pour lire les valeurs.

Axe X : taille de l'entrée n (0 → 30) · Axe Y : nombre d'opérations (échelle log)

📚 Catalogue des complexités

x = lst[42]   # toujours 1 opération

# n=1 000 000 → ~20 étapes seulement

for x in lst: ...   # n opérations

# n=1 000 000 → ~20 000 000 opérations

for i ...: for j ...: ...  # n² ops

# n=50 → 10^15 opérations… des années !

Tableau de comparaison numérique

🔬 Comment calculer la complexité ?

Voici la méthode systématique pour analyser n'importe quel algorithme :

Cas 1 — Boucles simples et imbriquées

# Une boucle → O(n)
for i in range(n):          # n fois
    traitement()              # O(1) → total O(n)

# Deux boucles indépendantes → O(n) + O(n) = O(n)
for i in range(n): ...       # O(n)
for j in range(n): ...       # O(n)
                               # total : O(2n) = O(n)

# Deux boucles imbriquées → O(n²)
for i in range(n):            # n fois
    for j in range(n):        # n fois
        traitement()          # O(1) → total O(n²)

# Boucle intérieure dépendant de i → toujours O(n²) !
for i in range(n):            # n fois
    for j in range(i):        # 0+1+2+...+(n-1) = n(n-1)/2
        traitement()          # → O(n²) quand même

Cas 2 — Division par 2 à chaque étape

# Si on divise par 2 à chaque itération → O(log n)
n_copie = n
while n_copie > 1:
    n_copie = n_copie // 2   # combien de fois ? log₂(n) fois
    traitement()

# Exemple : pour n=1024, la boucle tourne 10 fois
# 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

Cas 3 — Récursion : relations de récurrence

# Récursion linéaire : T(n) = T(n-1) + O(1)
def factorielle(n):
    if n <= 1: return 1        # T(1) = O(1)
    return n * factorielle(n-1) # T(n) = T(n-1) + O(1) → O(n)

# Diviser pour régner : T(n) = 2·T(n/2) + O(n)
def tri_fusion(lst):
    if len(lst) <= 1: return lst   # T(1) = O(1)
    m = len(lst) // 2
    g = tri_fusion(lst[:m])          # T(n/2)
    d = tri_fusion(lst[m:])          # T(n/2)
    return fusion(g, d)              # O(n) pour fusionner
# T(n) = 2·T(n/2) + O(n) → O(n log n)  (Théorème maître)

# Double récursion naïve : T(n) = 2·T(n-1) + O(1)
def fib_naif(n):
    if n <= 1: return n
    return fib_naif(n-1) + fib_naif(n-2) # → O(2ⁿ) 💀

⚡ Règles rapides à mémoriser

🎯 Exercices interactifs

Quelle est la complexité de chaque fonction ?

🚨 Pièges fréquents