#Évaluer la complexitéCopier le lien

Ordres de grandeur, notation grand-O, coûts en temps et mémoire : l'intuition d'abord, le formalisme ensuite.

#PrérequisCopier le lien

Les algorithmes de la page algorithmes servent d'exemples ; savoir compter les itérations d'une boucle suffit pour suivre.

#Objectifs d'apprentissageCopier le lien

• Estimer le nombre d'opérations d'un algorithme en fonction de la taille n de l'entrée.
• Classer les ordres de grandeur courants et sentir leurs écarts concrets.
• Écrire la relation de récurrence du coût d'un algorithme récursif et la résoudre.
• Distinguer coût en temps et coût en espace.
• Reconnaître le meilleur cas, le cas moyen et le pire cas, et savoir lequel communiquer.

#Pourquoi la complexité ?Copier le lien

La question pratique : mon programme tiendra-t-il le coup avec dix fois plus de données ? Mesurer des secondes sur une machine donnée ne répond pas : la machine change, le compilateur change, la charge change. La complexité algorithmique compte les opérations élémentaires en fonction de la taille de l'entrée, indépendamment de la machine. C'est un modèle, imparfait mais comparable d'un algorithme à l'autre et prédictif quand n grandit.

#La notation grand-OCopier le lien

Le grand-O décrit le comportement asymptotique : le taux de croissance du coût quand n tend vers l'infini. On ignore les constantes multiplicatives et les termes dominés : $3n^2 + 20n + 7$ s'écrit $O(n^2)$, car pour n grand, le terme $n^2$ écrase tout le reste.

#Ordres de complexité courantsCopier le lien

L'écart entre les lignes est la leçon : passer de O(n²) à O(n log n) sur n = 1 000 divise le travail par cent, quand accélérer la machine de 10 % ne gagne que 10 %.

#Ce que cela coûte vraimentCopier le lien

Compter les opérations ne dit rien tant qu'on ne les convertit pas en temps. Supposons qu'une machine traite une opération en une microseconde et qu'un programme doive énumérer toutes les parties d'un ensemble à $n$ éléments — il y en a $2^{n}$. Le temps total vaut alors $2^{n}$ microsecondes :

Le tableau mérite d'être lu deux fois. Entre $n = 20$ et $n = 60$, on n'a ajouté que 40 éléments — et le temps est passé d'une seconde à plus de trois millénaires. Une microseconde par opération est une hypothèse généreuse ; la conclusion ne dépend pas d'elle. Aucune amélioration matérielle ne compense une croissance exponentielle : gagner un facteur 1 000 sur la machine revient à ajouter 10 à $n$ avant que le temps redevienne le même.

#Quand la force brute ne suffit plus : le voyageur de commerceCopier le lien

Le cas d'école est le problème du voyageur de commerce. Toutes les villes d'une région sont reliées deux à deux ; on cherche le chemin le plus court permettant de toutes les parcourir sans jamais repasser deux fois par la même, en revenant au point de départ. L'algorithme naïf est évident : énumérer tous les parcours possibles, puis sélectionner le plus court.

Le seul problème est le nombre de parcours. Fixer la ville de départ, puis parcourir les $n-1$ autres dans un ordre quelconque, c'est choisir une permutation des $n-1$ villes restantes. Il y a donc

$(n-1)! \ \text{parcours à examiner}.$

Pour 12 villes, $11! = 39\,916\,800$ parcours : à une microseconde chacun, environ 40 secondes. Pour 20 villes, $19! \approx 1{,}2 \times 10^{17}$ : près de quatre mille ans. La factorielle croît plus vite que toute exponentielle — l'ordre de grandeur de $n!$ est $n^{n}$, que la formule de Stirling précise :

$n! \sim \sqrt{2\pi n}\;\left(\frac{n}{e}\right)^{n}.$

#ExemplesCopier le lien

• O(1) : accéder à un élément d'un tableau par son index ; tester l'appartenance dans un set.
• O(log n) : recherche dichotomique dans un tableau trié.
• O(n) : parcourir tous les éléments ; recherche linéaire ; trouver le maximum.
• O(n log n) : tri par comparaison optimal (tri fusion, tri rapide en moyenne, sorted de Python).
• O(n²) : boucles imbriquées parcourant toutes les paires ; tri à bulles ; tri par sélection.
• O(2ⁿ) : énumérer tous les sous-ensembles d'un ensemble ; Fibonacci récursif naïf.
• O(n!) : énumérer toutes les permutations d'un ensemble ; voyageur de commerce par force brute.

#Compter les opérations : deux exemplesCopier le lien

#Recherche linéaireCopier le lien

1def recherche_lineaire(tableau, element):2    for i in range(len(tableau)):3        if tableau[i] == element:4            return i5    return -1

Au pire cas, l'élément est absent : la boucle fait n comparaisons. Le coût en temps est O(n). L'espace utilisé est celui du tableau lui-même, plus un index : O(1) en espace supplémentaire.

#Recherche dichotomiqueCopier le lien

1def recherche_dichotomique(tableau, element):2    gauche, droite = 0, len(tableau) - 13    while gauche <= droite:4        milieu = (gauche + droite) // 25        if tableau[milieu] == element:6            return milieu7        elif tableau[milieu] < element:8            gauche = milieu + 19        else:10            droite = milieu - 111    return -1

Chaque itération fait une comparaison et divise l'espace de recherche par deux. Après k itérations, il reste $n / 2^k$ candidats ; la boucle s'arrête quand $n / 2^k \leq 1$, soit $k \approx \log_2 n$. Coût en temps O(log n), espace supplémentaire O(1).

#L'effet en pratiqueCopier le lien

1print([n * (n - 1) // 2 for n in (100, 1_000, 10_000)])2print([int(__import__('math').log2(n)) for n in (100, 1_000, 10_000)])

Sorties :

1[4950, 499500, 49995000]2[6, 9, 13]

Un algorithme quadratique fait environ 50 millions de paires à parcourir pour n = 10 000 ; le logarithmique s'en sort avec 13 étapes. À un million d'opérations par seconde, le premier demande 50 secondes, le second 13 microsecondes.

#Résoudre la récurrence d'un algorithme récursifCopier le lien

Compter les itérations d'une boucle suffit pour un algorithme itératif. Pour un algorithme récursif, le coût s'exprime par une relation de récurrence : le coût $T(n)$ est fonction des coûts $T(p)$ pour $p \lt n$. Résoudre cette relation, c'est en tirer le terme général — donc l'ordre de grandeur. Les équations de récurrence sont aux mathématiques discrètes ce que les équations différentielles sont aux mathématiques continues, et elles proviennent de deux sources : les définitions inductives, et les stratégies « diviser pour régner » qui utilisent la récursivité.

#Le vocabulaireCopier le lien

• Ordre : si $T(n)$ ne dépend que de $T(n-1)$, la relation est d'ordre 1 ; si elle dépend de $T(n-1)$ et $T(n-2)$, elle est d'ordre 2. Plus généralement, si $T(n)$ fait intervenir les termes d'indices entre $n-k$ et $n-1$, la relation est d'ordre $k$.
• Complète : tous les termes $T(p)$ pour $p \lt n$ interviennent.
• Linéaire : $T(n)$ est une combinaison linéaire des $T(p)$.
• De partition : $T(n)$ ne fait intervenir que des termes $T(n/p)$. Les algorithmes dichotomiques donnent des équations de partition avec $p = 2$.

#Exemple 1 : la recherche dichotomique (partition, $p = 2$)Copier le lien

Soit $T(n)$ le nombre de comparaisons de la recherche dichotomique dans un tableau trié de taille $n$, avec $n = 2^{k}$. Chaque appel fait une comparaison et relance la recherche sur la moitié du tableau :

$T(1) = 1, \qquad T(n) = 1 + T(n/2) \ \text{pour } n \gt 1.$

On opère le changement de variable $n = 2^{k}$, qui transforme la partition en suite récurrente ordinaire. Posons $S(k) = T(2^{k})$ :

$S(0) = 1, \qquad S(k) = 1 + S(k-1) \ \text{pour } k \gt 0.$

C'est une suite arithmétique de raison 1, donc $S(k) = k + 1$. Le changement de variable inverse ($k = \log_2 n$) donne

$T(n) = 1 + \log_2 n.$

Lecture. La récurrence de partition s'est ramenée à une récurrence linéaire par changement de variable : c'est la méthode générale annoncée par le cours. Le résultat $T(n) = 1 + \log_2 n$ est l'ordre $O(\log n)$ — mais il est maintenant démontré, et non seulement constaté.

#Exemple 2 : des droites dans le plan (arithmétique)Copier le lien

On trace $n$ droites dans le plan, deux à deux sécantes en des points distincts. Combien de régions délimitent-elles ? Notons $T(n)$ ce nombre. On observe $T(0) = 1$, $T(1) = 2$, $T(2) = 4$, $T(3) = 7$, et l'on comprend que la $n$-ième droite, coupée par les $n-1$ précédentes, ajoute $n$ régions :

$T(n) = T(n-1) + n \ \text{pour } n \gt 0.$

C'est le cas $a(n) = 1$ avec $b(n) = n$. La méthode de sommation consiste à écrire la relation aux rangs successifs puis à additionner membre à membre :

Les termes intermédiaires s'annulent et il reste

$T(n) = T(0) + \sum_{i=1}^{n} i = 1 + \frac{n(n+1)}{2}.$

Lecture. Croissance quadratique, $O(n^2)$. La somme des $n$ premiers entiers est le coût caché de tous les algorithmes « une boucle qui fait de plus en plus de travail ».

#Exemple 3 : les tours de Hanoï (géométrique)Copier le lien

Déplacer $n$ disques exige de déplacer $n-1$ disques sur un pilier intermédiaire, de déplacer le grand disque, puis de ramener les $n-1$ disques :

$T(0) = 0, \qquad T(n) = 2\,T(n-1) + 1 \ \text{pour } n \gt 0.$

On multiplie la relation au rang $n$ par 1, celle au rang $n-1$ par 2, celle au rang $n-2$ par 4, et ainsi de suite, puis on additionne :

En sommant, les termes intermédiaires s'annulent et il reste

$T(n) = 2^{n} T(0) + \sum_{i=0}^{n-1} 2^{i} = 0 + \left(2^{n} - 1\right) = 2^{n} - 1.$

Lecture. Croissance exponentielle : 64 disques demanderaient $2^{64} - 1 \approx 1{,}8 \times 10^{19}$ déplacements, soit près de six siècles à un déplacement par nanoseconde. La récurrence dit ici quelque chose de définitif, qu'aucune optimisation d'implémentation ne changera : le problème est intrinsèquement exponentiel.

#Exemple 4 : le tri rapide au pire cas (ordre 1 avec terme polynomial)Copier le lien

Le tri rapide, lorsque le pivot est systématiquement extrémal, ne retire qu'un élément par partition. Sa complexité $c(n)$ au pire cas vérifie

$c(2) = 3, \qquad c(n) = c(n-1) + n + 1 \ \text{pour } n \gt 2.$

La somme des relations donne $c(n) = c(2) + \sum_{k=4}^{n+1} k$, d'où

$c(n) = \frac{n^2 + 3n - 4}{2},$

soit $c(n) = \Theta(n^2)$. Lecture. C'est exactement l'écart entre le cas moyen $O(n \log n)$ et le pire cas $O(n^2)$ annoncé plus haut : la récurrence montre pourquoi le pire cas est quadratique — la profondeur de récursion devient $n$ au lieu de $\log_2 n$.

#Tableau récapitulatifCopier le lien

Ces quatre résolutions, et plusieurs autres, sont détaillées dans les annales corrigées.

#Temps contre espaceCopier le lien

La complexité en temps compte les opérations ; la complexité en espace compte la mémoire supplémentaire. Les deux s'échangent souvent :

• La dichotomique est O(1) en espace supplémentaire : elle ne garde que trois indices.
• Le tri fusion est O(n log n) en temps mais O(n) en espace : il recopie la moitié gauche avant de fusionner.
• La mémoïsation de Fibonacci naïf passe de O(2ⁿ) en temps à O(n), en payant O(n) en mémoire pour le cache.

Il n'y a pas de bon choix universel : sur mobile ou dans un navigateur, la mémoire est parfois la ressource la plus rare ; en calcul intensif, c'est le temps. L'important est de connaître les deux nombres avant de décider.

#Meilleur cas, cas moyen, pire casCopier le lien

Le même algorithme n'a pas un seul coût :

• Pire cas : l'entrée la plus défavorable. C'est la garantie qu'on promet : « jamais plus de O(n log n) ».
• Meilleur cas : l'entrée la plus favorable. Rarement utile, sauf à documenter un raccourci (recherche linéaire sur le premier élément : O(1)).
• Cas moyen : l'espérance sur des entrées typiques, souvent ce qu'on observe en pratique.

Exemples : le tri rapide est O(n log n) en moyenne mais O(n²) au pire cas (pivot systématiquement extrémal). La recherche linéaire est O(1) au mieux (élément en première position) et O(n) au pire. Quand on annonce une complexité sans préciser, c'est le pire cas qu'on doit avoir en tête.

#Règles de calcul rapidesCopier le lien

• Boucles successives : les coûts s'additionnent, le maximum domine. for puis for sur n éléments : O(n) + O(n) = O(n).
• Boucles imbriquées : les coûts se multiplient. for dans for : O(n) × O(n) = O(n²).
• Diviser le problème par deux à chaque étape et faire un travail constant : O(log n).
• Diviser en deux et faire un travail linéaire par étape : O(n log n).
• Une fonction à k appels récursifs imbriqués sur une entrée réduite de 1 : souvent O(2ⁿ) ou pire (Fibonacci naïf).
• Récurrence de la forme $T(n) = T(n-1) + b(n)$ : sommer $b$ sur les rangs successifs. Si $b$ est constant, la solution est linéaire ; si $b(n) = n$, elle est quadratique.
• Récurrence de la forme $T(n) = a\,T(n-1) + b$ avec $a \gt 1$ : suite géométrique, croissance exponentielle en $a^{n}$.
• Récurrence de partition $T(n) = 1 + T(n/2)$ : changement de variable $n = 2^{k}$, qui la ramène à une suite arithmétique en $k$ ; solution $O(\log n)$.

#ExercicesCopier le lien

1. Classez par ordre de croissance : $O(n)$, $O(2^n)$, $O(\log n)$, $O(n^2)$, $O(n \log n)$, $O(1)$, $O(n!)$.
2. Donnez la complexité en temps et en espace supplémentaire de recherche_dichotomique, puis du tri par sélection (deux boucles imbriquées, échanges en place).
3. Un traitement prend 2 secondes sur n = 1 000 avec un algorithme O(n²). Combien de temps attendre pour n = 3 000 ? Et si l'algorithme était O(n) ?
4. Énumérez tous les sous-ensembles d'un ensemble de 20 éléments : pourquoi O(2ⁿ) rend-il la chose hors de portée ?
5. Un algorithme récursif divise son entrée en deux et fait une comparaison constante. Écrivez sa relation de récurrence, résolvez-la par changement de variable, et donnez son ordre.
6. Le coût d'un algorithme vérifie $T(0) = 0$ et $T(n) = 2\,T(n-1) + 1$. Résolvez la récurrence et dites, en une phrase, ce que le résultat implique pour $n = 64$.
7. Un programme énumère les permutations de $n$ éléments pour trouver la meilleure. Combien de cas examine-t-il pour $n = 12$ ? Pourquoi est-ce pire que d'énumérer les sous-ensembles ?