Complexité des algorithmes

L'étude d'un algorithme $A$ commence par le choix d'une taille $n$ de l'entrée : un entier qui mesure la donnée et que l'on annonce avant tout calcul (longueur d'une liste, nombre de lignes et de colonnes d'une matrice, nombre de chiffres d'un entier, nombre de sommets et d'arêtes d'un graphe). Une opération élémentaire est une opération dont on convient qu'elle s'exécute en un temps borné, indépendant de $n$ : une affectation, une comparaison de deux nombres, une opération arithmétique sur des nombres de taille bornée, un accès L[i]. Le coût $C_A(e)$ de l'algorithme sur une entrée $e$ est le nombre d'opérations élémentaires qu'il exécute sur $e$. Compter des opérations et non des secondes rend l'étude indépendante de la machine, du langage et de la charge du processeur. Le modèle est une convention que l'on écrit : en Python, L[i] et len(L) sont élémentaires, mais x in L et L[a:b] ne le sont pas.

Soit $E_n$ l'ensemble des entrées de taille $n$, supposé non vide et fini. La complexité dans le pire des cas de $A$ est $C_{\max}(n) = \max_{e \in E_n} C_A(e)$ et sa complexité dans le meilleur des cas est $C_{\min}(n) = \min_{e \in E_n} C_A(e)$. En français : $C_{\max}(n)$ est le plus grand nombre d'opérations que $A$ puisse exécuter sur une entrée de taille $n$ ; toute entrée de taille $n$ coûte au plus $C_{\max}(n)$, et au moins une entrée coûte exactement $C_{\max}(n)$. Sauf mention contraire, « la complexité de $A$ » désigne $C_{\max}$ : c'est la seule des trois complexités qui garantisse quelque chose sur toutes les entrées.

On munit l'ensemble fini $E_n$ d'une loi de probabilité $p$, c'est-à-dire d'une famille de réels $\big(p(e)\big)_{e \in E_n}$ positifs de somme $1$. La complexité en moyenne est alors $C_{\text{moy}}(n) = \sum_{e \in E_n} p(e) \, C_A(e)$, l'espérance du coût sous cette loi. Le point que les copies oublient : la moyenne dépend de la loi, qui n'est pas une propriété de l'algorithme mais une hypothèse sur les données, et qui doit donc être annoncée (« on suppose les $n!$ ordres de la liste équiprobables », « on suppose la valeur cherchée présente, à une position uniforme »). Sans cette phrase, un calcul de moyenne ne veut rien dire.

Propriété : soit $n$ tel que $E_n$ soit fini et non vide, et soit $p$ une loi de probabilité sur $E_n$. Alors $C_{\min}(n) \leq C_{\text{moy}}(n) \leq C_{\max}(n)$. La démonstration tient en une ligne : pour toute entrée $e$, $C_{\min}(n) \leq C_A(e) \leq C_{\max}(n)$ ; on multiplie par $p(e) \geq 0$, on somme sur $E_n$ et on utilise $\sum_{e \in E_n} p(e) = 1$. Conséquence : une majoration du pire des cas majore la moyenne, donc $C_{\max} = O(f)$ entraîne $C_{\text{moy}} = O(f)$. La réciproque est fausse : une moyenne petite n'interdit pas un pire des cas beaucoup plus grand, comme le montre le tri rapide, en $\Theta(n \log n)$ en moyenne et $\Theta(n^2)$ dans le pire des cas (voir le thème Récursivité et diviser pour régner).

Soient $(u_n)$ et $(v_n)$ deux suites de réels positifs, avec $v_n > 0$ à partir d'un certain rang. On pose :
$u_n = O(v_n)$ lorsque $\exists C > 0, \ \exists n_0 \in \mathbb{N}, \ \forall n \geq n_0, \ u_n \leq C v_n$ ;
$u_n = \Omega(v_n)$ lorsque $\exists c > 0, \ \exists n_0 \in \mathbb{N}, \ \forall n \geq n_0, \ u_n \geq c v_n$ ;
$u_n = \Theta(v_n)$ lorsque les deux ont lieu.
En français : $O$ est une majoration à une constante près et à partir d'un certain rang, $\Omega$ une minoration, $\Theta$ un ordre de grandeur exact. L'écriture $u_n = O(v_n)$ est un abus universel : elle signifie « $u$ appartient à l'ensemble $O(v)$ » et ne se lit pas de droite à gauche. Les mêmes notations sont définies en toute généralité, pour des suites de signe quelconque, dans le thème Négligeabilité, domination et équivalents (bloc Analyse 2), où $u_n = O(v_n)$ s'écrit $u_n = v_n \varepsilon_n$ avec $(\varepsilon_n)$ bornée ; pour des suites positives, les deux définitions coïncident.

Propriété : soient $u, u', v, v'$ des suites de réels positifs, strictement positives à partir d'un certain rang.
1) Réflexivité et transitivité : $u = O(u)$, et si $u = O(v)$ et $v = O(w)$, alors $u = O(w)$.
2) Constantes : pour tout réel $\lambda > 0$, $u = O(\lambda v)$ équivaut à $u = O(v)$. On n'écrit donc jamais $O(2n + 3)$, mais $O(n)$.
3) Somme : si $u = O(v)$ et $u' = O(v')$, alors $u + u' = O(v + v')$ ; de plus $v + v' = \Theta\big(\max(v, v')\big)$, puisque $\max(v,v') \leq v + v' \leq 2 \max(v, v')$. Dans une somme, seul le plus grand terme compte.
4) Produit : si $u = O(v)$ et $u' = O(v')$, alors $u u' = O(v v')$ : c'est la règle des boucles imbriquées.
5) $\Theta$ est une relation d'équivalence (voir le thème Relations d'équivalence et d'ordre, bloc Fondements 1), ce qui autorise à parler de la classe d'un algorithme.
En revanche, les $O$ ne se soustraient pas : de $u = O(n^2)$ et $u' = O(n^2)$ on ne peut pas conclure $u - u' = O(1)$, comme le montrent $u_n = 2n^2$ et $u'_n = n^2$, dont la différence vaut $n^2$. Les deux majorations ne donnent rien de mieux sur la différence que sur la somme, à savoir $u - u' = O(n^2)$.

Ligne fautive : « Tout tri par comparaison effectue au moins $O(n \log n)$ comparaisons. »
La notation $O$ est une majoration : « au moins une majoration » ne veut rien dire. La phrase fautive est vérifiée par un algorithme qui ferait trois comparaisons, puisque la suite constante $3$ est bien un $O(n \log n)$ : elle n'exclut donc rien du tout, alors qu'elle prétend établir une borne inférieure. C'est $\Omega$ qu'il faut écrire.
Version correcte : « Tout tri par comparaison effectue $\Omega(n \log n)$ comparaisons dans le pire des cas », c'est-à-dire : il existe $c > 0$ et un rang $n_0$ tels que, pour tout $n \geq n_0$, le nombre de comparaisons dans le pire des cas soit au moins $c \, n \log n$. Ce résultat est démontré dans le thème Algorithmes élémentaires et preuve de programmes.
Même famille : on n'écrit jamais $O(2n + 3)$ ni $O(3n^2)$, puisque les constantes multiplicatives et les termes dominés disparaissent ; on écrit $O(n)$ et $O(n^2)$.

Propriété : soient $\alpha, \beta$ des réels avec $0 \leq \alpha < \beta$, $k \in \mathbb{N}$ et $a > 1$. Alors $n^{\alpha} = O(n^{\beta})$ et $n^{\beta}$ n'est pas un $O(n^{\alpha})$ ; $(\ln n)^k = O(n^{\alpha})$ dès que $\alpha > 0$ ; $n^{\beta} = O(a^n)$ ; $a^n = O(n!)$ ; $n! = O(n^n)$. Ces comparaisons sont celles des croissances comparées du thème Limites de fonctions (bloc Analyse 1), appliquées à des suites. Elles se résument par la chaîne de l'encadré, où chaque terme est négligeable devant le suivant.
Base du logarithme : pour tous $a, b > 1$, $\log_a n = \frac{\ln n}{\ln a}$, donc $\log_a n = \Theta(\log_b n)$. La classe $\Theta(\log n)$ ne dépend pas de la base : c'est pourquoi on écrit $\log n$ sans base dans une complexité, alors qu'un comptage exact d'itérations, lui, réclame une base précise.

Les classes rencontrées en première année, avec l'effet d'un doublement de la taille sur le temps de calcul.
$\Theta(1)$, constante : accès L[i], len(L), ajout L.append(x), en $\Theta(1)$ amorti (voir la carte « Le coût amorti de append est constant ») ; le temps ne dépend pas de la taille de la donnée.
$\Theta(\log n)$, logarithmique : boucle qui divise la taille par deux à chaque tour, recherche dichotomique (thème Algorithmes élémentaires et preuve de programmes) ; le temps augmente d'une constante.
$\Theta(n)$, linéaire : un parcours de la donnée, somme, maximum, x in L ; le temps double.
$\Theta(n \log n)$, quasi-linéaire : tris efficaces, sorted ; le temps est un peu plus que doublé.
$\Theta(n^2)$, quadratique : deux boucles imbriquées sur la donnée, tris élémentaires ; le temps est multiplié par $4$.
$\Theta(n^3)$, cubique : trois boucles imbriquées, produit de deux matrices $n \times n$ ; le temps est multiplié par $8$.
$\Theta(2^n)$, exponentielle : énumération des parties d'un ensemble à $n$ éléments ; le temps double quand $n$ augmente de $1$.
$\Theta(n!)$, factorielle : énumération des permutations ; intraitable au-delà d'une dizaine d'éléments.
Repère d'ordre de grandeur, pour une machine qui exécute environ $10^8$ opérations élémentaires par seconde, un interpréteur Python étant plutôt dix fois plus lent : en une seconde environ, on traite $n = 10^6$ en linéaire et en quasi-linéaire, $n = 10^4$ en quadratique, $n = 500$ en cubique, $n = 25$ en exponentiel et $n = 11$ en factoriel. Ces repères se retiennent : ils disent à eux seuls si une idée d'algorithme mérite d'être programmée.

Ligne fautive : « L'algorithme $A$ est en $O(n)$ et l'algorithme $B$ en $O(n^2)$, donc $A$ est plus rapide que $B$. »
Deux erreurs dans la même phrase. D'abord, une classe ne dit rien des constantes : contre-exemple chiffré avec $T_A(n) = 1000n$ et $T_B(n) = n^2$, pour $n = 100$ on a $T_A(100) = 100\,000$ et $T_B(100) = 10\,000$, donc $B$ est dix fois plus rapide ; $A$ ne l'emporte que pour $n > 1000$. Ensuite, $O$ est une majoration : dire que $B$ est en $O(n^2)$ n'interdit pas à $B$ d'être en $\Theta(1)$, auquel cas rien n'empêche $B$ de l'emporter à toute taille.
Version correcte : « $A$ est en $\Theta(n)$ et $B$ en $\Theta(n^2)$, donc à partir d'une certaine taille $A$ est plus rapide que $B$ ; pour des tailles bornées, seule une mesure départage. » Et c'est bien ce que l'on veut : la classe décide du passage à l'échelle, pas du chronomètre sur un petit exemple.

Les sommes qui reviennent dans presque tout calcul de complexité. Elles sont démontrées dans le thème Sommes et produits finis (bloc Fondements 1) et se retrouvent par récurrence (thème Récurrence simple, bloc Fondamental). On retient surtout leur classe : la deuxième est $\Theta(n^2)$, la troisième $\Theta(n^3)$, l'avant-dernière $\Theta(\log n)$ et la dernière $\Theta(n \log n)$.

Quand l'utiliser : dès qu'un énoncé demande « la complexité », « le nombre d'opérations », « le coût » d'une fonction écrite devant soi, ou qu'il faut départager deux programmes qui font la même chose.
1) Annoncer la taille. Écrire « Notons $n$ la longueur de la liste valeurs » avant tout calcul. Sans cette phrase, le reste n'a pas de sens : un même programme est linéaire en le nombre de coefficients et quadratique en le nombre de lignes d'une matrice carrée.
2) Fixer l'opération comptée. « On compte les comparaisons entre éléments », « on compte les additions ». Les autres opérations se comptent alors à un facteur constant près, donc la classe ne change pas.
3) Découper le programme en blocs : ce qui précède la boucle, le corps de la boucle, ce qui la suit. Donner à chaque bloc un coût, en opérations comptées.
4) Traduire chaque boucle en une somme. Une boucle for i in range(a, b) exécute $b - a$ tours si $b \geq a$, et aucun sinon ; si le corps du tour $i$ coûte $c_i$, le coût de la boucle est $\sum_{i=a}^{b-1} c_i$. Une boucle imbriquée donne une somme de sommes.
5) Calculer la somme avec le formulaire, puis conclure en $\Theta$ : on garde le terme dominant et on jette les constantes.
6) Vérifier : ajouter un compteur dans le programme, l'exécuter sur deux ou trois tailles et comparer au résultat exact trouvé. Un comptage faux se voit en dix secondes ; il ne se devine pas.

Compter exactement les additions effectuées par la fonction suivante sur une liste de longueur $n$, puis donner sa complexité temporelle.

def somme_comptee(valeurs):
    """Renvoie la somme des éléments de valeurs et le nombre d'additions effectuées.
    Précondition : valeurs est une liste de nombres."""
    total = 0
    additions = 0
    for v in valeurs:
        total = total + v
        additions = additions + 1
    return total, additions

Notons $n$ la longueur de la liste valeurs. On compte les additions portant sur les éléments de la liste, c'est-à-dire les évaluations de total + v.
Les deux affectations total = 0 et additions = 0 s'exécutent une fois et ne coûtent aucune addition.
La boucle for v in valeurs exécute exactement $n$ tours, un par élément de la liste, et chaque tour évalue une fois total + v.
Le coût en additions comptées vaut donc $C(n) = \sum_{k=1}^{n} 1 = n$.
En comptant cette fois toutes les opérations élémentaires, chaque tour en exécute un nombre borné (deux additions, deux affectations, un avancement de la boucle), disons au plus $\lambda$ ; hors boucle, le coût est borné par une constante $\mu$. Ainsi $n \leq C_{\text{tot}}(n) \leq \lambda n + \mu$, donc $C_{\text{tot}}(n) = \Theta(n)$.
La complexité temporelle de somme_comptee est linéaire, $\Theta(n)$, dans tous les cas : aucune entrée ne fait sortir de la boucle par avance, donc le meilleur et le pire des cas coïncident.
Vérification : l'appel somme_comptee([3, 1, 4, 1, 5]) affiche (14, 5), l'appel somme_comptee([]) affiche (0, 0), et sur list(range(1000)) le compteur vaut 1000, conformément à $C(n) = n$.
À retenir : on annonce la taille, on dit quelle opération on compte, on traduit la boucle en une somme, puis on conclut en $\Theta$ en remarquant que le corps du tour coûte un nombre borné d'opérations.

Ligne fautive : « Cette fonction est en $\Theta(n)$. »
Tant que l'on n'a pas dit ce que $n$ mesure, la phrase ne dit rien, et elle est souvent fausse. Contre-exemple : une fonction qui parcourt une liste de $n$ chaînes de caractères et compare chacune à une chaîne donnée n'est pas en $\Theta(n)$ ; si les chaînes ont $\ell$ caractères, une comparaison en coûte $\Theta(\ell)$ dans le pire des cas, et le total est $\Theta(n \ell)$. Pour $n = 1\,000$ chaînes de $\ell = 10^{6}$ caractères, l'écart entre $10^{3}$ et $10^{9}$ opérations sépare l'instantané d'une dizaine de secondes.
De la même famille : « ce calcul sur une matrice est en $\Theta(n^2)$ » n'a pas de sens tant que l'on n'a pas dit si $n$ est le côté de la matrice ou son nombre de coefficients, les deux réponses différant d'un carré.
Version correcte : « Notons $n$ le nombre de chaînes et $\ell$ leur longueur maximale. Dans le pire des cas, la fonction est en $\Theta(n\ell)$ ; si l'on convient qu'une comparaison de deux chaînes est une opération élémentaire, elle est en $\Theta(n)$. »
Réflexe : une complexité s'écrit avec ses paramètres nommés, et le modèle de coût s'annonce en même temps qu'eux.

Ligne fautive : « La boucle for d in range(2, n) fait moins de $n$ tours, donc ce test de primalité est linéaire, donc efficace. »
La taille d'un entier $n$ est le nombre de chiffres ou de bits qu'il faut pour l'écrire, c'est-à-dire $\Theta(\log n)$, et non $n$. Un coût de $n$ opérations est donc exponentiel en la taille de l'entrée. Contre-exemple chiffré : un entier de $30$ chiffres vaut environ $10^{30}$ ; à $10^{8}$ opérations par seconde, la boucle demanderait plus de $10^{14}$ années, alors que l'entrée tient sur une ligne.
Version correcte : « La boucle effectue $n - 2$ tours : le coût est $\Theta(n)$ en la valeur de $n$, c'est-à-dire exponentiel en son nombre de chiffres. » S'arrêter à $\sqrt{n}$ divise l'exposant par deux et rend le calcul praticable bien plus loin, sans changer la nature exponentielle du coût ; ces algorithmes sont repris dans le thème Algorithmes d'arithmétique et de polynômes.
Réflexe : quand l'entrée est un entier, écrire explicitement laquelle des deux tailles on choisit, la valeur ou le nombre de chiffres, et ne jamais les mélanger dans une même phrase.

Quand l'utiliser : devant deux boucles ou plus emboîtées, et en particulier lorsque les bornes de la boucle interne dépendent de l'indice de la boucle externe, ce qui est le cas le plus fréquent en concours.
1) Nommer les indices et leurs bornes, de l'extérieur vers l'intérieur : for i in range(n) puis for j in range(i + 1, n).
2) Compter les tours de la boucle interne, à $i$ fixé. Une boucle range(a, b) fait $\max(b - a, 0)$ tours : ici $n - (i+1) = n - i - 1$ tours.
3) Sommer sur l'indice externe : le nombre total de passages dans le corps est $\sum_{i=0}^{n-1} (n - i - 1)$. Le changement d'indice $k = n - i - 1$, qui parcourt $\{0, \dots, n-1\}$, donne $\sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}$.
4) Multiplier par le coût d'un passage, borné par une constante si le corps ne contient ni boucle, ni appel coûteux, ni opération cachée comme x in L ou L[a:b].
5) Conclure en $\Theta$. Deux repères qui dispensent du calcul quand seule la classe est demandée : si les deux bornes valent $n$, la classe est $\Theta(n^2)$ ; si la boucle interne est triangulaire, elle est encore $\Theta(n^2)$, car $\frac{n(n-1)}{2} = \Theta(n^2)$. La forme triangulaire ne fait gagner qu'un facteur $2$, jamais une classe.
6) Se méfier d'une boucle dont l'indice ne progresse pas de $1$ : while i < n: i = 2 * i fait $\Theta(\log n)$ tours, pas $\Theta(n)$.

Déterminer le nombre exact de passages dans le corps de la boucle interne de la fonction suivante, puis sa complexité temporelle.

def compter_paires(n):
    """Renvoie le nombre de couples (i, j) d'entiers tels que 0 <= i < j < n.
    Précondition : n est un entier naturel."""
    compteur = 0
    for i in range(n):
        for j in range(i + 1, n):
            compteur = compteur + 1
    return compteur

La taille de l'entrée est l'entier $n$ lui-même. On compte les passages dans le corps de la boucle interne, c'est-à-dire les exécutions de compteur = compteur + 1.
Soit $i \in \{0, \dots, n-1\}$ fixé. La boucle for j in range(i + 1, n) parcourt les entiers de $i+1$ à $n-1$ : elle effectue $n - i - 1$ tours, ce nombre étant positif car $i \leq n - 1$.
Le nombre total de passages vaut donc $N(n) = \sum_{i=0}^{n-1} (n - i - 1)$.
On pose $k = n - i - 1$ : quand $i$ parcourt $\{0, \dots, n-1\}$, l'entier $k$ parcourt $\{0, \dots, n-1\}$, et la somme devient $N(n) = \sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}$.
Chaque passage exécute un nombre borné d'opérations élémentaires (une addition, une affectation, un avancement de boucle), et le reste de la fonction coûte un nombre borné d'opérations. Il existe donc deux constantes $\lambda > 0$ et $\mu > 0$ telles que, pour tout $n \geq 1$, $N(n) \leq C(n) \leq \lambda N(n) + \mu$.
Or $\frac{n(n-1)}{2} = \Theta(n^2)$, car pour tout $n \geq 2$ on a $\frac{n^2}{4} \leq \frac{n(n-1)}{2} \leq \frac{n^2}{2}$.
La fonction compter_paires est donc de complexité quadratique, $\Theta(n^2)$, dans tous les cas.
Vérification : [compter_paires(n) for n in range(7)] affiche [0, 0, 1, 3, 6, 10, 15], qui sont bien les valeurs de $\frac{n(n-1)}{2}$, et compter_paires(100) affiche 4950, égal à $\frac{100 \times 99}{2}$.
À retenir : on compte les tours de la boucle interne à indice externe fixé, on somme, et l'on conclut en $\Theta$ ; une boucle triangulaire reste quadratique.

Ligne fautive : « La fonction contient deux boucles sur la liste, donc son coût est quadratique. »
Deux boucles successives coûtent $\Theta(n) + \Theta(n) = \Theta(n)$, car dans une somme seul le terme dominant compte. Deux boucles imbriquées coûtent $\Theta(n) \times \Theta(n) = \Theta(n^2)$, car c'est la règle du produit qui s'applique. Le nombre de boucles écrites ne décide de rien : c'est l'indentation qui tranche, et elle seule, selon que la seconde boucle est dans le corps de la première ou après elle.
Contre-exemple chiffré : parcourir deux fois de suite une liste de $10^6$ éléments demande $2 \times 10^6$ opérations, soit une fraction de seconde ; les parcourir de façon imbriquée en demande $10^{12}$, soit plusieurs heures sur la même machine.
Version correcte : « La fonction contient deux boucles successives, chacune en $\Theta(n)$, donc son coût est $\Theta(n) + \Theta(n) = \Theta(n)$ : elle est linéaire. » Et dans le cas imbriqué : « la boucle interne est exécutée $n$ fois, chaque exécution coûtant $\Theta(n)$, donc le coût est $\Theta(n^2)$. »
Réflexe : avant de compter, redessiner la structure du programme en retrait, une boucle par niveau, et compter les niveaux.

Propriété : soit $n$ un entier naturel non nul. La boucle while n > 0: n = n // 2 effectue exactement $\lfloor \log_2 n \rfloor + 1$ tours. En particulier, ce nombre de tours est $\Theta(\log n)$. L'hypothèse $n \geq 1$ est indispensable : pour $n = 0$ la boucle n'est jamais entrée et effectue $0$ tour, alors que $\log_2 0$ n'est pas défini ; pour $n < 0$, la division entière vers le bas donne -1 // 2 == -1, et la boucle while n != 0 ne terminerait jamais. C'est ce résultat, et lui seul, qui fait qu'un algorithme divisant sa donnée par deux à chaque tour est logarithmique : la recherche dichotomique et l'exponentiation rapide (voir les thèmes Algorithmes élémentaires et preuve de programmes et Algorithmes d'arithmétique et de polynômes) reposent dessus.

Soit $n$ un entier naturel non nul. Démontrer que la fonction suivante renvoie $\lfloor \log_2 n \rfloor + 1$.

def nombre_de_divisions(n):
    """Renvoie le nombre de passages dans la boucle qui divise n par deux jusqu'à 0.
    Précondition : n est un entier naturel non nul."""
    assert n >= 1
    passages = 0
    while n > 0:
        n = n // 2
        passages = passages + 1
    return passages

Notons $p(n)$ la valeur renvoyée par nombre_de_divisions(n), pour $n \geq 1$.
Montrons d'abord un lemme : pour tout entier $n \geq 2$, $\big\lfloor \log_2 \lfloor n/2 \rfloor \big\rfloor = \lfloor \log_2 n \rfloor - 1$.
Posons $k = \lfloor \log_2 n \rfloor$. Comme $n \geq 2$, on a $k \geq 1$, et par définition de la partie entière, $2^k \leq n < 2^{k+1}$.
En divisant par $2$ : $2^{k-1} \leq \frac{n}{2} < 2^{k}$. L'entier $2^{k-1}$ minore $\frac{n}{2}$, donc il minore aussi sa partie entière : $2^{k-1} \leq \lfloor n/2 \rfloor$. Par ailleurs $\lfloor n/2 \rfloor \leq \frac{n}{2} < 2^{k}$.
Ainsi $2^{k-1} \leq \lfloor n/2 \rfloor < 2^{k}$, ce qui donne $\big\lfloor \log_2 \lfloor n/2 \rfloor \big\rfloor = k - 1$, et le lemme est démontré.
Montrons maintenant par récurrence forte (voir le thème Récurrence forte, bloc Fondamental) la propriété $P(n)$ : « $p(n) = \lfloor \log_2 n \rfloor + 1$ », pour tout entier $n \geq 1$.
Initialisation. Pour $n = 1$ : la condition n > 0 est vraie, l'affectation donne n = 1 // 2 = 0, le compteur passe à $1$, puis la condition est fausse. Donc $p(1) = 1$, et $\lfloor \log_2 1 \rfloor + 1 = 0 + 1 = 1$ : $P(1)$ est vraie.
Hérédité. Soit $n \geq 2$ ; supposons $P(m)$ vraie pour tout entier $m$ tel que $1 \leq m < n$. Le premier tour remplace n par $\lfloor n/2 \rfloor$ et incrémente le compteur ; comme $n \geq 2$, on a $1 \leq \lfloor n/2 \rfloor < n$. Les tours suivants sont exactement ceux qu'effectuerait l'appel sur $\lfloor n/2 \rfloor$, donc $p(n) = 1 + p\big(\lfloor n/2 \rfloor\big)$.
L'hypothèse de récurrence appliquée à $\lfloor n/2 \rfloor$ donne $p\big(\lfloor n/2 \rfloor\big) = \big\lfloor \log_2 \lfloor n/2 \rfloor \big\rfloor + 1$, puis le lemme donne $p(n) = 1 + \big(\lfloor \log_2 n \rfloor - 1\big) + 1 = \lfloor \log_2 n \rfloor + 1$ : $P(n)$ est vraie.
Par récurrence forte, pour tout entier $n \geq 1$, $p(n) = \lfloor \log_2 n \rfloor + 1$.
Chaque tour coûtant un nombre borné d'opérations élémentaires, la complexité de nombre_de_divisions est $\Theta(\log n)$.
Vérification : pour n valant 1, 2, 3, 4, 7, 8, 1000, la fonction affiche [1, 2, 2, 3, 3, 4, 10], et l'égalité avec $\lfloor \log_2 n \rfloor + 1$ a été testée sans exception pour tout $n$ de $1$ à $100\,000$.
À retenir : un encadrement par deux puissances de deux transforme une partie entière de logarithme en inégalités d'entiers, et une boucle qui divise par deux se traite par récurrence forte sur la valeur de la variable.

Quand l'utiliser : l'énoncé demande de démontrer une comparaison, et non de la deviner : « montrer que $C(n) = \Theta(n^2)$ », « montrer que cet algorithme n'est pas linéaire ». Le seul argument recevable est l'exhibition des constantes de la définition.
1) Écrire ce qu'il faut produire. Pour un $O$ : une constante $C > 0$ et un rang $n_0$ tels que $\forall n \geq n_0, \ u_n \leq C v_n$. Pour un $\Omega$ : une constante $c > 0$ et un rang. Pour un $\Theta$ : les deux.
2) Majorer terme à terme. Chaque morceau de $u_n$ se majore par un multiple de $v_n$, à partir d'un rang que l'on note : pour $n \geq 1$, $n \leq n^2$ et $1 \leq n^2$.
3) Additionner et annoncer les constantes. « Ainsi, pour tout $n \geq 1$, $u_n \leq 15 n^2$ : avec $C = 15$ et $n_0 = 1$, on a $u_n = O(n^2)$. » Une preuve qui ne nomme ni $C$ ni $n_0$ n'est pas une preuve.
4) Minorer en jetant les termes positifs, ce qui est presque toujours immédiat : $3n^2 + 5n + 7 \geq 3n^2$.
5) Pour réfuter un $O$, raisonner par l'absurde (voir le thème Raisonnement par l'absurde, bloc Fondamental) : supposer données les constantes $C$ et $n_0$, puis choisir un entier $n \geq n_0$ qui contredit l'inégalité. Un contre-exemple sur une seule valeur de $n$ ne suffit pas, puisque la définition n'exige l'inégalité qu'à partir d'un rang.
6) Ne jamais dériver ni intégrer un $O$, et ne jamais le soustraire : seules les règles de la carte des règles de calcul sont autorisées.

Un algorithme a pour coût $C(n) = 3n^2 + 5n + 7$ opérations sur une entrée de taille $n \geq 1$. Démontrer que $C(n) = \Theta(n^2)$, puis que $C(n)$ n'est pas un $O(n)$.
Majoration. Soit $n \geq 1$. Alors $n \leq n^2$ et $1 \leq n^2$, donc $5n \leq 5n^2$ et $7 \leq 7n^2$.
En additionnant ces deux inégalités et $3n^2 \leq 3n^2$, on obtient $C(n) \leq 3n^2 + 5n^2 + 7n^2 = 15 n^2$.
Ainsi, avec $C_1 = 15$ et $n_0 = 1$, on a $\forall n \geq n_0, \ C(n) \leq C_1 n^2$, donc $C(n) = O(n^2)$.
Minoration. Soit $n \geq 1$. Les réels $5n$ et $7$ sont positifs, donc $C(n) = 3n^2 + 5n + 7 \geq 3n^2$.
Ainsi, avec $c_1 = 3$ et $n_0 = 1$, on a $\forall n \geq n_0, \ C(n) \geq c_1 n^2$, donc $C(n) = \Omega(n^2)$.
Les deux comparaisons étant établies, $C(n) = \Theta(n^2)$.
Montrons enfin que $C(n)$ n'est pas un $O(n)$.
Supposons par l'absurde que $C(n) = O(n)$ : il existe un réel $C_2 > 0$ et un entier $n_1$ tels que, pour tout $n \geq n_1$, $3n^2 + 5n + 7 \leq C_2 n$.
Pour un tel $n$, on a en particulier $3n^2 \leq C_2 n$, et comme $n \geq 1 > 0$, on peut diviser par $n$ : $3n \leq C_2$, donc $n \leq \frac{C_2}{3}$.
Cette majoration vaudrait pour tout entier $n \geq n_1$. Or l'entier $N = \max\left(n_1, \left\lfloor \frac{C_2}{3} \right\rfloor + 1\right)$ vérifie $N \geq n_1$ et $N > \frac{C_2}{3}$, ce qui contredit la majoration obtenue.
L'hypothèse est donc fausse : $C(n)$ n'est pas un $O(n)$, autrement dit cet algorithme n'est pas linéaire.
À retenir : une majoration se rédige en exhibant $C$ et $n_0$, une minoration en jetant les termes positifs, et une réfutation en choisissant, par l'absurde, un entier assez grand au-delà du rang supposé.

Quand l'utiliser : dès que le programme contient une sortie anticipée (return ou break dans une boucle), un test dont l'issue dépend des données, ou un appel conditionnel. Si le programme parcourt toujours toute la donnée, les trois complexités coïncident et il faut le dire, en une phrase, plutôt que de s'en taire.
1) Décrire $E_n$ : « les listes de $n$ entiers deux à deux distincts », « les listes de $n$ éléments contenant la valeur cherchée ».
2) Repérer ce qui fait varier le coût : la position de l'élément cherché, l'ordre initial de la liste, la profondeur atteinte avant la sortie.
3) Meilleur des cas : exhiber une entrée de coût minimal et justifier la minoration pour toutes les autres. « Si valeurs[0] vaut cible, une seule comparaison suffit ; et toute entrée en exige au moins une, car la boucle est entrée au moins une fois dès que $n \geq 1$. »
4) Pire des cas : exhiber une entrée de coût maximal et justifier la majoration pour toutes les autres. Une famille d'entrées explicite vaut mieux qu'un « dans le pire des cas, on parcourt tout ».
5) Moyenne : annoncer la loi, découper $E_n$ selon la valeur du coût, puis calculer l'espérance $\sum_e p(e) C_A(e)$. Vérifier l'encadrement par le meilleur et le pire des cas : un résultat hors de cet intervalle est faux.
6) Conclure en disant laquelle on donne : « la complexité dans le pire des cas est $\Theta(n)$ », jamais « la complexité est $\Theta(n)$ » quand les trois diffèrent.

Donner les complexités dans le meilleur des cas, dans le pire des cas et en moyenne de la fonction suivante, en nombre de comparaisons, sur une liste de longueur $n \geq 1$.

def position_comptee(valeurs, cible):
    """Renvoie le couple formé du plus petit indice i tel que valeurs[i] vaut cible
    (ou -1 s'il n'y en a pas) et du nombre de comparaisons effectuées.
    Précondition : valeurs est une liste."""
    comparaisons = 0
    for i in range(len(valeurs)):
        comparaisons = comparaisons + 1
        if valeurs[i] == cible:
            return i, comparaisons
    return -1, comparaisons

On compte les comparaisons valeurs[i] == cible. La correction de cette recherche séquentielle relève du thème Algorithmes élémentaires et preuve de programmes ; on n'établit ici que son coût.
Soit $e$ une entrée de taille $n$. Si la valeur cible figure dans la liste, notons $i(e)$ le plus petit indice où elle figure : la boucle s'arrête au tour $i(e)$ et exécute exactement $i(e) + 1$ comparaisons. Si elle n'y figure pas, la boucle va jusqu'au bout et exécute exactement $n$ comparaisons.
Meilleur des cas. Pour toute entrée, la boucle est entrée au moins une fois puisque $n \geq 1$, donc au moins une comparaison est exécutée : $C_{\min}(n) \geq 1$. L'entrée valeurs = [0, 1, ..., n-1] avec cible = 0 donne $i(e) = 0$, donc une comparaison. Ainsi $C_{\min}(n) = 1 = \Theta(1)$.
Pire des cas. Pour toute entrée, le nombre de comparaisons vaut $i(e) + 1 \leq n$ ou $n$ : il est majoré par $n$. L'entrée valeurs = [0, 1, ..., n-1] avec cible = -1 atteint cette valeur. Ainsi $C_{\max}(n) = n = \Theta(n)$.
Moyenne. On suppose la valeur cible présente dans la liste, à une position $i$ suivant la loi uniforme sur $\{0, \dots, n-1\}$ : chaque position a la probabilité $\frac{1}{n}$, et le coût vaut alors $i+1$.
Donc $C_{\text{moy}}(n) = \sum_{i=0}^{n-1} \frac{1}{n} (i+1) = \frac{1}{n} \sum_{k=1}^{n} k = \frac{1}{n} \times \frac{n(n+1)}{2} = \frac{n+1}{2}$.
Contrôle : $1 \leq \frac{n+1}{2} \leq n$ pour tout $n \geq 1$, l'encadrement par le meilleur et le pire des cas est bien respecté.
En moyenne, la recherche parcourt donc la moitié de la liste, et $C_{\text{moy}}(n) = \Theta(n)$ : la moyenne fait gagner un facteur $2$, pas une classe.
Si l'on change de loi et que l'on suppose la valeur absente avec la probabilité $q \in [0,1]$, et sinon uniformément placée, la moyenne devient $q n + (1-q) \frac{n+1}{2}$, qui est encore $\Theta(n)$ : la classe résiste au changement de loi, la constante non.
Vérification : sur [10, 20, 30, 40, 50], les appels pour les cibles 10, 30, 50 et 99 affichent [(0, 1), (2, 3), (4, 5), (-1, 5)], et la moyenne des comparaisons sur les cinq valeurs présentes vaut 3.0, égale à $\frac{5+1}{2}$.
À retenir : on justifie le meilleur et le pire des cas par une entrée explicite et par une inégalité valable pour toutes, et l'on n'écrit pas une moyenne sans avoir annoncé la loi qui la définit.

Ligne fautive : « Il y a deux cas, l'un coûte $1$ opération et l'autre $n$, donc en moyenne le coût vaut $\frac{n+1}{2}$. »
Faire la moyenne des cas revient à les supposer équiprobables, ce qui est une hypothèse sur les données, jamais un fait. La complexité en moyenne est une espérance : chaque coût est pondéré par la probabilité de son cas.
Contre-exemple chiffré : si le cas coûteux survient avec la probabilité $\frac{1}{n}$, le coût moyen vaut $\frac{1}{n} \times n + \left(1 - \frac{1}{n}\right) \times 1 = 2 - \frac{1}{n}$, donc moins de deux opérations. Pour $n = 1\,000$, la bonne valeur est voisine de $2$, et la valeur fautive de $500$ : elles ne sont pas même de la même classe, l'une étant $\Theta(1)$ et l'autre $\Theta(n)$.
Version correcte : « On suppose que le cas coûteux survient avec la probabilité $p$. Le coût moyen vaut alors $p \, n + (1 - p) \times 1$. » On annonce la loi, on pondère, puis on contrôle l'encadrement $C_{\min}(n) \leq C_{\text{moy}}(n) \leq C_{\max}(n)$, qui rattrape la plupart des erreurs de pondération.

La complexité spatiale d'un algorithme est le nombre de cases mémoire qu'il occupe, exprimé en fonction de la taille $n$ de l'entrée. On distingue l'espace total, qui compte l'entrée, et l'espace auxiliaire, qui ne compte que ce que l'algorithme alloue en plus : c'est l'espace auxiliaire que l'on donne, car l'entrée est là de toute façon. Un algorithme est dit en place lorsque son espace auxiliaire est $O(1)$, c'est-à-dire borné indépendamment de $n$ : il modifie la donnée sans en construire de copie. Attention aux coûts cachés : une liste en compréhension, une tranche L[a:b], une concaténation L1 + L2 et sorted(L) allouent une nouvelle liste, alors que L.sort() range les éléments de la liste elle-même au lieu d'en construire une nouvelle. Ce tri n'est pas en place au sens de la définition ci-dessus : l'algorithme employé par Python utilise un tampon de fusion pouvant atteindre $n/2$ cases, soit un espace auxiliaire $\Theta(n)$. En récursivité, la pile d'appels compte dans l'espace auxiliaire (voir le thème Récursivité et diviser pour régner).

Comparer les complexités temporelle et spatiale des deux fonctions suivantes, qui renversent l'ordre des éléments d'une liste de longueur $n$.

def renverser_en_place(valeurs):
    """Renverse la liste valeurs sur place et ne renvoie rien.
    Précondition : valeurs est une liste."""
    n = len(valeurs)
    for i in range(n // 2):
        valeurs[i], valeurs[n - 1 - i] = valeurs[n - 1 - i], valeurs[i]


def renversee(valeurs):
    """Renvoie une nouvelle liste contenant les éléments de valeurs dans l'ordre inverse."""
    resultat = []
    for i in range(len(valeurs) - 1, -1, -1):
        resultat.append(valeurs[i])
    return resultat

Temps. La boucle de renverser_en_place effectue $\lfloor n/2 \rfloor$ tours, chacun coûtant un nombre borné d'opérations élémentaires (deux lectures, deux écritures) : son coût est $\Theta(n)$.
La boucle de renversee effectue $n$ tours, chacun coûtant un nombre borné d'opérations, l'appel à append étant en $\Theta(1)$ amorti : son coût est également $\Theta(n)$.
Les deux fonctions sont donc linéaires en temps, et le facteur $2$ qui les sépare ne se lit pas dans la classe.
Espace. renverser_en_place alloue les deux variables n et i et un couple temporaire : son espace auxiliaire est $O(1)$, elle est en place.
renversee construit une liste de $n$ éléments : son espace auxiliaire est $\Theta(n)$.
Les deux fonctions n'ont pas non plus la même spécification : la première modifie la liste de l'appelant et renvoie None, la seconde laisse la liste intacte et renvoie une nouvelle liste. Le choix se fait sur cette différence d'abord, sur l'espace ensuite.
Vérification : après l = [1, 2, 3, 4, 5] puis renverser_en_place(l), la liste l vaut [5, 4, 3, 2, 1] ; renversee([1, 2, 3, 4, 5]) renvoie [5, 4, 3, 2, 1] et renverser_en_place([]) renvoie None sans erreur.
À retenir : deux fonctions de même classe temporelle peuvent différer du tout au tout en espace ; on annonce l'espace auxiliaire, et l'on dit si l'algorithme est en place.

Ligne fautive : « La fonction est en $\Theta(n)$ en temps, donc elle traitera sans difficulté un milliard d'éléments. »
Une classe temporelle ne dit rien de la mémoire. Contre-exemple chiffré : une liste Python de $10^{9}$ éléments occupe, rien que pour les références qu'elle contient, de l'ordre de huit octets par élément sur une machine de $64$ bits, soit environ huit gigaoctets, sans compter les objets pointés. Le programme n'échoue pas en fin de calcul : il échoue à l'allocation, ou bien la machine se met à échanger avec le disque et le temps mesuré n'a plus rien à voir avec le temps calculé.
De la même famille : construire [[0] * n for i in range(n)] pour $n = 100\,000$ demande $10^{10}$ cases, ce qu'aucune machine ordinaire n'offre, quelle que soit la classe temporelle du calcul qui suit.
Version correcte : « La fonction est en $\Theta(n)$ en temps et en $\Theta(n)$ en espace auxiliaire ; pour $n = 10^{9}$, c'est l'espace qui interdit le calcul. » Quand seul un résumé de la donnée est demandé, une somme, un maximum ou un nombre d'occurrences, on parcourt la donnée sans la stocker et l'espace auxiliaire retombe à $\Theta(1)$.
Réflexe : donner deux classes, une pour le temps et une pour l'espace auxiliaire, et dire si l'algorithme est en place.

Quand l'utiliser : après avoir calculé la complexité, pour confirmer la classe trouvée, comparer deux versions d'un même programme ou estimer un temps de calcul. Jamais à la place du calcul : une mesure ne démontre rien, elle donne un indice.
1) Mesurer un appel long avec time.perf_counter(), l'horloge de précision : on relève l'instant avant et après, et on soustrait. On n'emploie pas time.time(), dont la résolution est trop grossière et qui peut reculer si l'horloge du système est réajustée.
2) Construire la donnée hors de la mesure. Si list(range(n)) est appelé entre les deux relevés, c'est lui que l'on chronomètre.
3) Répéter et garder le minimum, jamais la moyenne : une perturbation extérieure ne peut qu'allonger une mesure, donc le minimum est la valeur la plus proche du coût réel.

import time


def duree(fonction, argument, repetitions=5):
    """Renvoie la plus petite durée, en secondes, observée sur repetitions appels de
    fonction sur argument.
    Précondition : fonction s'appelle avec un seul argument."""
    durees = []
    for essai in range(repetitions):
        debut = time.perf_counter()
        fonction(argument)
        durees.append(time.perf_counter() - debut)
    return min(durees)

4) Mesurer un appel court avec timeit, qui répète l'instruction un grand nombre de fois et neutralise le coût de l'horloge : timeit.repeat(instruction, globals=globals(), number=k, repeat=r) renvoie $r$ durées, chacune pour $k$ exécutions, dont on prend le minimum. L'argument globals=globals() est indispensable pour que l'instruction voie les variables du programme.
5) Faire varier la taille géométriquement et tabuler le rapport de deux durées consécutives, ce qui élimine la constante multiplicative inconnue.

def table_de_doublement(fonction, fabrique, tailles):
    """Affiche, pour chaque taille n, la durée mesurée et son rapport à la précédente.
    Précondition : fabrique(n) construit une donnée de taille n, et chaque taille de
    la liste tailles est le double de la précédente."""
    precedente = None
    for n in tailles:
        t = duree(fonction, fabrique(n))
        if precedente is None:
            print(n, round(t, 4), "-")
        else:
            print(n, round(t, 4), round(t / precedente, 2))
        precedente = t


def liste_croissante(n):
    """Renvoie la liste des entiers de 0 à n-1, tous distincts."""
    return list(range(n))


def identite(n):
    """Renvoie n : fabrique à utiliser quand la donnée est la taille elle-même."""
    return n

6) Lire le rapport avec prudence. Il est bruité, il se dégrade quand la donnée cesse de tenir dans les mémoires rapides de la machine, et il ne distingue pas $\Theta(n)$ de $\Theta(n \log n)$, dont les rapports valent $2$ et un peu plus de $2$.

Propriété : soit $\lambda > 0$ et soit $T$ le temps de calcul d'un programme, supposé donné par un modèle exact.
1) Si $T(n) = \lambda n^{d}$ avec $d \geq 0$, alors pour tout $n \geq 1$, $\frac{T(2n)}{T(n)} = 2^{d}$ : le rapport vaut $2$ pour un programme linéaire, $4$ pour un quadratique, $8$ pour un cubique, $1$ pour un programme à temps constant.
2) Si $T(n) = \lambda n \log_2 n$, alors pour tout $n \geq 2$, $\frac{T(2n)}{T(n)} = 2\left(1 + \frac{1}{\log_2 n}\right)$, qui est strictement supérieur à $2$ et tend vers $2$ : un programme quasi-linéaire se distingue très mal d'un programme linéaire sur des mesures.
3) Si $T(n) = \lambda a^{n}$ avec $a > 1$, alors $\frac{T(n+1)}{T(n)} = a$ : c'est un seul élément de plus qui multiplie le temps, et doubler la taille le multiplie par $a^{n}$, c'est-à-dire l'élève au carré à la constante $\lambda$ près.
Attention : ces égalités portent sur le modèle $T$, pas sur la classe. Savoir seulement que $T = \Theta(n^2)$ ne donne aucune limite au rapport : la fonction qui vaut $n^2$ pour $n$ pair et $2n^2$ pour $n$ impair est bien $\Theta(n^2)$, et son rapport $\frac{T(2n)}{T(n)}$ vaut alternativement $4$ et $2$. Une table de doublement est donc un indice, jamais une démonstration.