La complexité algorithmique

📄 Ressources du cours

🎥 Vidéos recommandées

• 🇫🇷 Algorithmique (14/14) - Complexité des algorithmes

  Mohamed Chiny · 06:27 · 202k vues — Le calcul de la complexité d'un algorithme (complexité asymptotique) consiste à évaluer la quantité des ressources utilisées par l'algorithme en question (ou...

• 🇫🇷 Méthode de calcul de la complexité d'un algorithme | Rachid Guerraoui

  Wandida, EPFL · 11:05 · 192k vues — Cette leçon donne une méthode pratique pour déterminer la complexité d'un algorithme. Elle consiste à voir comment l'algorithme évolue en augmentant la taill...

• 🇬🇧 Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)

  CS Dojo · 36:22 · 960k vues — Big O notation and time complexity, explained. Check out Brilliant.org (https://brilliant.org/CSDojo/), a website for learning math and computer science conc...

1. Généralités sur la complexité

Une mesure de complexité estime le temps de calcul ou l'espace mémoire utilisé par un algorithme.

Notations

• A : un algorithme
• D(n) : l'ensemble des données de taille n
• P(d) : probabilité de la donnée d
• Coût_A(d) : coût de l'algorithme pour la donnée d

2. Calcul — algorithmes non récursifs

Sans structures de contrôle

Dénombrer simplement les opérations successives :

def celsius_fahrenheit(C):
   F = C * 1.8 + 32     # 2 op arithmetiques + 1 affectation
   return F            # T(n) = 3, complexite constante

Structures conditionnelles

La complexité dépend des données. Trois formes de complexité :

Exemple — structure conditionnelle

def f(x, y):
   if x > y:
      h = x * x          # 1 op arith + 1 affectation
   else:
      h = y * y + 1      # 2 op arith + 1 affectation
   return h
# Comparaison : 1
# Pire des cas (else) : 1 + 3 = 4
# Meilleur cas (if)   : 1 + 2 = 3
# Moyen (proba 0.5)   : 1 + 0.5×2 + 0.5×3 = 3.5

Structures itératives

Temps total = somme du coût du test + corps de la boucle + gestion du compteur, multiplié par le nombre d'itérations.

def somme_1(n):
   S = 0
   for i in range(n):
      S = S + i            # n iterations -> O(n)
   return S

def somme_2(n):
   S = n * (n + 1) // 2    # formule directe -> O(1)
   return S

Deux fonctions équivalentes en résultat, mais somme_1 est linéaire et somme_2 est constante. Le choix d'algorithme prime sur l'optimisation locale.

3. Comportement asymptotique — O, Ω, Θ

Trois notations pour comparer le comportement à l'infini de deux fonctions définies sur ℕ à valeurs dans ℝ⁺.

O(g(n)) = {f : ℕ → ℝ⁺ | ∃ k > 0 et n₀ ≥ 0 tels que ∀ n ≥ n₀, 0 ≤ f(n) ≤ k · g(n)}

Ω(g(n)) = {f : ℕ → ℝ⁺ | ∃ k > 0 et n₀ ≥ 0 tels que ∀ n ≥ n₀, 0 ≤ k · g(n) ≤ f(n)}

Θ(g(n)) = {f : ℕ → ℝ⁺ | ∃ k₁ > 0, k₂ > 0, n₀ ≥ 0 tels que ∀ n ≥ n₀, 0 ≤ k₁·g(n) ≤ f(n) ≤ k₂·g(n)}

Classes de complexité usuelles

À partir de la complexité quadratique, on quitte le « scalable ». Au-delà du cubique, on est dans l'algorithmique de recherche, pas en pratique.

4. Algorithmes récursifs simples

Un algorithme récursif décompose le problème en sous-problèmes de même nature. Sa complexité est une suite définie par récurrence.

Cas 1 — Factorielle

def factorielleRecursive(n):
   if n == 0:
      return 1
   else:
      return n * factorielleRecursive(n - 1)

Cas 2 — Tours de Hanoï

def hanoi(de, vers, via, n):
   if n == 1:
      print(de, "vers", vers)
   else:
      hanoi(de, via, vers, n - 1)
      print(de, "vers", vers)
      hanoi(via, vers, de, n - 1)

5. Suites récurrentes linéaires

un+2 = a · un+1 + b · un

Équation caractéristique

On résout x² − a·x − b = 0 :

Cas Fibonacci

fib(n) = if n == 0 : 0
         else if n == 1 : 1
         else : fib(n-1) + fib(n-2)

Équation récurrente (en ignorant les constantes) :

T(n) = T(n-1) + T(n-2)

Avec l'équation caractéristique x² − x − 1 = 0, on obtient le nombre d'or φ = (1+√5)/2 :

T(n) = (1/√5) · (φⁿ − (1−φ)ⁿ)

Donc T(n) = Θ(φⁿ) ≈ Θ(1.618ⁿ), exponentiel.

PGCD — un cas plus subtil

def pgcd(x, y):
   if y == 0:
      return x
   else:
      return pgcd(y, x mod y)

Pas d'équation récurrente directe — on s'appuie sur Fibonacci. On montre par récurrence que si pgcd(x, y) fait k divisions avec x > y > 0, alors x ≥ Fk+2 (le (k+2)-ième terme de Fibonacci).

En passant au log avec φ : k ≤ logφ(√5 + 1) − 3.

6. Diviser pour régner

Tri par fusion

1. Diviser le tableau en deux moitiés
2. Trier récursivement les deux moitiés
3. Fusionner les deux tableaux triés
4. Coût de la fusion : Θ(n)

Équation récurrente : T(n) = 2·T(n/2) + Θ(n) avec T(1) = 1.

Théorème Master

T(n) = ⎧ Θ(nd)              si a < bd
       ⎨ Θ(nd · log(n))      si a = bd
       ⎩ Θ(nlog_b(a))        si a > bd

Interprétation :

• n = taille du problème
• a = nombre de sous-problèmes
• n/b = taille de chaque sous-problème
• f(n) = coût de la subdivision et de la combinaison

Application : tri par fusion

Tri par fusion : T(n) = 2 · T(n/2) + Θ(n) → a=2, b=2, d=1. Donc bd = 2 = a ⇒ T(n) = Θ(n · log(n)), quasi-linéaire.

Application : multiplication de matrices (Strassen)

Décomposition en sous-matrices : T(n) = 8·T(n/2) + Θ(n²) → a=8, b=2, d=2. bd=4 < a=8 ⇒ T(n) = Θ(nlog₂(8)) = Θ(n³). Pas d'amélioration par rapport à l'algorithme naïf. (Strassen avec 7 récursions au lieu de 8 donne Θ(nlog₂(7)) ≈ Θ(n2.81) — sous-cubique).

7. Correction d'un algorithme — invariants

Démarche pour prouver un algorithme itératif

1. Analyser les boucles, en commençant par la boucle la plus interne
2. Concevoir un invariant de boucle
3. Prouver l'invariant par récurrence :
   • Montrer qu'il est vrai avant la première itération
   • Montrer que s'il est vrai à l'itération k, il l'est à l'itération k+1
4. Utiliser l'invariant pour prouver la terminaison
5. Utiliser l'invariant pour prouver que le résultat est correct

Exemple — somme d'un tableau

def somme(t):
   S = 0
   n = len(t)
   for i in range(n):
      S += t[i]
   return S

Invariant proposé : à la fin de l'itération i, S contient la somme des i premiers éléments de t :

Si = Σk=0i-1 t[k]

Preuve par récurrence :

• Base : S₁ = S_initial + t[0] = t[0]. La propriété est vraie pour i = 1.
• Hérédité : si Si = Σ t[k] jusqu'à l'index i-1, alors Si+1 = Si + t[i] = Σ jusqu'à i. ✓

L'algorithme termine après n itérations. La complexité est Θ(n).

Validité d'un algorithme récursif

Trois choses à prouver :

1. Cas d'arrêt : le résultat produit est correct
2. Hérédité : sous hypothèse que les appels récursifs sont corrects, le résultat l'est aussi
3. Convergence : toute séquence d'appels conduit à un cas d'arrêt

★ Réviser le chapitre

🃏 Flashcards

↻ Tout retourner

✎ Quiz éclair — classer les complexités

❓ Q/R