01 — Complexité Algorithmique : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~50 min

---

Table des matières

1. Introduction : pourquoi analyser ?
2. Définitions : Big-O, Omega, Theta
3. Règles de calcul
4. Complexités classiques
5. Complexité spatiale
6. Analyse amortie
7. Résolution de récurrences
8. Analyse empirique vs théorique
9. Diagrammes de comparaison
10. Résumé

---

1. Introduction : pourquoi analyser ?

La complexité d'un algorithme mesure sa croissance en fonction de la taille n de l'entrée. Deux raisons fondamentales :

1. Prédictibilité : estimer le temps d'exécution sans exécuter.
2. Comparaison : choisir entre deux algorithmes indépendamment de la machine.

Point crucial : on ne mesure pas des secondes (dépend de la machine) mais des opérations élémentaires en fonction de n. La machine n'introduit qu'une constante multiplicative.

1.1 Exemple fondateur

def somme_liste(liste):
    total = 0
    for x in liste:
        total += x
    return total

• Opérations : 1 initialisation + n itérations (1 addition + 1 incrément) + 1 retour.
• Total : 1 + 3n + 1 = 3n + 2 opérations.
• Pour n = 10^6 : 3 × 10^6 opérations. Pour n = 10^9 : 3 × 10^9.
• Le facteur 3 est une constante. Ce qui compte : le temps est proportionnel à n → O(n).

---

2. Définitions : Big-O, Omega, Theta

2.1 Notation Big-O — borne supérieure

Définition : f(n) = O(g(n)) s'il existe des constantes c > 0 et n₀ ≥ 1 telles que pour tout n ≥ n₀ : 0 ≤ f(n) ≤ c · g(n).

Intuition : à partir d'un seuil n₀, f est toujours sous c·g. C'est une borne supérieure asymptotique.

Diagramme en cours de génération...

⚠️ Big-O est une borne supérieure, pas une égalité. Un algorithme O(n²) peut très bien être aussi O(n) — il faut chercher la borne la plus serrée (tight bound) : pour 3n+2, le plus serré est O(n).

2.2 Notation Big-Omega — borne inférieure

Définition : f(n) = Ω(g(n)) s'il existe c > 0 et n₀ ≥ 1 tels que pour tout n ≥ n₀ : f(n) ≥ c · g(n) ≥ 0.

Intuition : à partir de n₀, f est toujours au-dessus de c·g. Exemple : 3n + 2 = Ω(n) (et même = Ω(1), mais le plus serré est Ω(n)).

2.3 Notation Big-Theta — borne serrée

Définition : f(n) = Θ(g(n)) si à la fois f(n) = O(g(n)) et f(n) = Ω(g(n)).

Intuition : f et g croissent à la même vitesse : c₁·g(n) ≤ f(n) ≤ c₂·g(n) pour n ≥ n₀.

3n + 2 = Θ(n)   ✓ (entre 3n et 5n pour n ≥ 1)
3n + 2 = Θ(n²)  ✗ (pas de c₁ tel que c₁·n² ≤ 3n+2)

2.4 Tableau récapitulatif

2.5 Limites et rapports

Pour comparer f et g, on calcule souvent : lim f(n)/g(n).

Exemple : f = 7n² + 3n, g = n². f/g → 7 → f = Θ(n²).

---

3. Règles de calcul

3.1 Règle de la somme

Si deux travaux s'exécutent séquentiellement (l'un après l'autre) :

T(n) = T₁(n) + T₂(n)  →  T(n) = O(max(g₁, g₂))

Intuition : le plus coûteux domine.

for x in liste:              # O(n)
    ...
for i in liste:              # O(n²)  → domine
    for j in liste:
        ...
# Total : O(n) + O(n²) = O(n²)

3.2 Règle du produit

Si deux travaux sont imbriqués (boucle dans boucle) :

T(n) = T₁(n) × T₂(n)  →  T(n) = O(g₁ × g₂)

for i in range(n):        # n fois
    for j in range(m):    # m fois
        pass              # O(1)
# Total : O(n × m). Si m = n : O(n²)

3.3 Règle de composition

f(g(n)) : si g(n) ≤ O(h(n)), alors f(g(n)) ≤ O(f(h(n))).

Exemple : f(x) = 2^x, g(n) = 3n → 2^(3n) = (2³)^n = 8^n = O(8^n).

3.4 Règle de domination (hiérarchie)

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

Une fonction est dominée par une fonction de rang supérieur : O(n) + O(n²) = O(n²).

3.5 Cas particuliers

• Logarithmes : toutes les bases sont équivalentes : log₂(n) = Θ(log₁₀(n)) car log₂ n = log₁₀ n / log₁₀ 2 (constante).
• Exposants : 2^n et 3^n ne sont pas équivalents : 3^n = ω(2^n).
• Polynômes vs exponentielles : pour tout k fixé, n^k = o(2^n).
• Log vs polynôme : (log n)^k = o(n^ε) pour tout k, ε > 0.

3.6 Règles de simplification

O(1) constant   — pas de boucle
O(log n)        — division par 2 à chaque étape (recherche binaire)
O(n)            — une boucle simple
O(n log n)      — boucle + division (tri par fusion)
O(n²)           — boucle imbriquée (tri à bulles)
O(2^n)          — exploration de tous les sous-ensembles
O(n!)           — exploration de toutes les permutations

---

4. Complexités classiques

4.1 O(1) — Constant

def acces(liste, i):
    return liste[i]   # accès direct, indépendant de n

Applications : accès indexé, opérations arithmétiques, opérations sur hash table.

4.2 O(log n) — Logarithmique

def recherche_binaire(liste, cible):
    gauche, droite = 0, len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        if liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

À chaque étape, on divise l'espace par 2 : après k étapes, il reste n/2^k éléments. Termine quand n/2^k = 1 → k = log₂ n.

Nombre de comparaisons : au plus ⌊log₂(n)⌋ + 1. Pour n = 10^9 → seulement 30 comparaisons.

4.3 O(n) — Linéaire

Une boucle parcourant les n éléments. Exemples : recherche linéaire, somme, maximum.

4.4 O(n log n) — Quasi-linéaire

Divide-and-conquer où chaque niveau coûte O(n) sur log₂ n niveaux. Exemples : merge sort, heap sort, quick sort (moyenne).

4.5 O(n²) — Quadratique

Boucles imbriquées. Exemples : tri à bulles, tri par insertion, tri par sélection, produit de matrices naïf.

4.6 O(2^n) — Exponentielle

Exploration de tous les sous-ensembles. Exemple : Fibonacci naïf, sous-ensemble-sum, SAT brut.

4.7 O(n!) — Factorielle

Exploration de toutes les permutations. Exemple : voyageur de commerce brut (n = 20 → 2,4 × 10^18 opérations → impossible).

4.8 Tableau des complexités (n = 10^6 opérations/s)

---

5. Complexité spatiale

La complexité spatiale mesure la mémoire supplémentaire (hors entrée) utilisée.

5.1 Exemples

def somme(liste):            # espace O(1) : une seule variable
    total = 0
    for x in liste:
        total += x
    return total

def double(liste):            # espace O(n) : nouvelle liste
    return [x * 2 for x in liste]

def fibonacci_memo(n):       # espace O(n) : dictionnaire
    memo = {}
    ...

5.2 Récursion : espace de pile

Chaque appel récursif empile un cadre (frame). La profondeur de récursion détermine l'espace :

def factorielle(n):
    return 1 if n <= 1 else n * factorielle(n - 1)   # O(n) espace (n frames)

5.3 Trade-off classique

---

6. Analyse amortie

L'analyse amortie étudie le coût moyen d'une opération sur une séquence d'opérations, même si certaines opérations sont très coûteuses ponctuellement.

6.1 Tableau dynamique (dynamic array)

En Python, une liste s'agrandit dynamiquement. Stratégie : doubler la capacité quand pleine.

• Coût d'insertion « normale » : O(1).
• Coût quand la table est pleine (doubling) : O(n) — on copie les n éléments.

Séquence de n insertions : copies totales = 1 + 2 + 4 + … + n/2 + n = 2n - 1 = O(n).

Coût amorti : O(n)/n = O(1) par insertion. Les insertions rares à O(n) sont « diluées ».

Diagramme en cours de génération...

6.2 Méthodes d'analyse

6.3 Compteur binaire (incremental counter)

Incrémenter un compteur binaire de n bits : l'opération simple coûte O(1), mais l'opération sur un compteur de k bits où k bits basculent... En séquence de n incréments :

• Le bit 0 bascule n fois.
• Le bit 1 bascule n/2 fois.
• Le bit i bascule n/2^i fois.

Coût total = Σ n/2^i = 2n → O(n) pour n incréments, soit O(1) amorti.

6.4 Exemple en code

class TableauDynamique:
    def __init__(self):
        self.capacite = 1
        self.taille = 0
        self.data = [None] * self.capacite

    def ajouter(self, x):
        if self.taille == self.capacite:
            self.capacite *= 2
            nouveau = [None] * self.capacite
            for i in range(self.taille):      # O(n) ponctuel
                nouveau[i] = self.data[i]
            self.data = nouveau
        self.data[self.taille] = x
        self.taille += 1

---

7. Résolution de récurrences

7.1 Écrire une récurrence

Le temps T(n) d'un algorithme récursif s'écrit :

T(n) = a·T(n/b) + f(n)

• a : nombre de sous-problèmes.
• n/b : taille de chaque sous-problème.
• f(n) : coût de division + combinaison.

Exemple merge sort : T(n) = 2·T(n/2) + O(n) (2 moitiés + fusion linéaire).

7.2 Méthode de substitution

1. Deviner la forme (souvent O(n^k) ou O(n^k log n)).
2. Supposer qu'elle est vraie pour les petites tailles.
3. Remplacer et vérifier par induction.

Exemple : T(n) = 2·T(n/2) + n. Devinons T(n) = O(n log n).

T(n) = 2·T(n/2) + n
     ≤ 2·(c·(n/2)·log(n/2)) + n
     = c·n·log(n/2) + n
     = c·n·log n - c·n + n
     ≤ c·n·log n   (pour c ≥ 1)

Vérifié → T(n) = Θ(n log n).

7.3 Méthode de l'arbre de récurrence

On déplie la récurrence en arbre et on somme les coûts par niveau.

Diagramme en cours de génération...

Pour T(n) = 2T(n/2) + n :

• Niveau 0 : coût n
• Niveau 1 : 2 × (n/2) = n
• Niveau k : 2^k × (n/2^k) = n
• Nombre de niveaux : log₂ n (on divise jusqu'à 1)
• Total : n × log₂ n = Θ(n log n)

7.4 Master Theorem

Pour T(n) = a·T(n/b) + f(n) avec a ≥ 1, b > 1, on compare f(n) à n^(log_b a).

Exemples :

7.5 Limites du Master theorem

Ne s'applique pas si f(n) ne suit pas une puissance de n comparée à n^(log_b a) (ex. : f(n) = n·log n avec log_b a = 1 — le « gap » polylog). Utiliser alors l'arbre ou la substitution.

---

8. Analyse empirique vs théorique

8.1 Comparaison

8.2 Protocole de benchmark

1. Varier n : puissances de 2 ou ×10 (100, 1000, 10⁴, …).
2. Répliquer : exécuter au moins 5 fois, prendre la médiane.
3. Échauffer (warm-up) pour la JIT et les caches.
4. Définir l'entrée : pire cas, meilleur cas, cas moyen.
5. Vérifier la cohérence : le rapport T(2n)/T(n) doit approcher le rapport théorique.

8.3 Exemple Python

import time, random

def chronometrer(fonction, args, repetitions=5):
    temps = []
    for _ in range(repetitions):
        debut = time.perf_counter()
        fonction(*args)
        temps.append(time.perf_counter() - debut)
    return sorted(temps)[len(temps) // 2]   # médiane

# Recherche linéaire : T(2n)/T(n) ≈ 2 (linéaire)
# Recherche binaire : T(2n)/T(n) ≈ 1 (logarithme)

8.4 Limites du théorique

• Les constantes cachées peuvent rendre un O(n²) plus rapide qu'un O(n log n) pour les petites n.
• La localité de cache (cache locality) : le merge sort est O(n log n) mais utilise plus de mémoire que le quick sort.
• Les entrées réelles ne sont pas le pire cas mathématique.

---

9. Diagrammes de comparaison

9.1 Croissance des fonctions

Diagramme en cours de génération...

9.2 Temps estimés (n = 10⁶, 10⁹ op/s)

---

10. Résumé

1. Big-O = borne supérieure ; Ω = borne inférieure ; Θ = borne serrée.
2. Règles : somme = max, produit = multiplication, composition, hiérarchie de domination.
3. Hiérarchie : 1 < log n < √n < n < n log n < n² < n³ < 2^n < n!.
4. Espace : mesurer la mémoire additionnelle ; récursion → O(profondeur).
5. Amorti : tableau dynamique et compteur binaire : O(1) amorti.
6. Récurrences : substitution, arbre, Master theorem (3 cas).
7. Empirique vs théorique : complémentaires ; le théorique domine pour comparer.

---

Exercices d'auto-évaluation

1. Montrez que 5n³ + 2n² + 7 = Θ(n³).
2. Calculez la complexité : for i: for j < i: O(1). Réponse : Σ i = n(n-1)/2 = O(n²).
3. Résolvez T(n) = 4T(n/2) + n par Master theorem. (log_b a = 2, cas 1 → Θ(n²).)
4. Un algorithme double son temps quand n est multiplié par 2. Quelle complexité ?
5. Expliquez pourquoi le coût amorti d'un push de tableau dynamique est O(1).
6. Donnez la complexité spatiale de la recherche binaire récursive.

Passez au quiz puis aux TP.