L'essentiel à connaître
Pour trouver la complexité d'un algorithme, compte combien de fois il exécute une opération élémentaire (une comparaison, une addition) pour une entrée de taille $n$, dans le pire des cas, puis garde seulement le terme qui grandit le plus vite, sans sa constante. Une boucle sur une liste de $n$ éléments coûte $O(n)$ ; deux boucles imbriquées de $n$ tours chacune coûtent $n \times n$ tours, donc $O(n^2)$. Deux boucles qui se suivent s'additionnent : $n + n = 2n$, ce qui reste $O(n)$. Si la boucle intérieure dépend de l'extérieure, additionne ses tours un par un avant de simplifier.
La complexité logarithmique, $O(\log n)$, apparaît quand chaque tour divise le problème par deux, ou double un compteur jusqu'à $n$. La recherche dichotomique en est l'exemple type : dans une liste triée, elle examine l'élément du milieu, puis ne garde que la moitié où la valeur peut se trouver. Elle coûte $O(\log n)$, quand une recherche séquentielle peut devoir regarder les $n$ éléments, en $O(n)$ (cours de L1 d'Étienne Lozes, Université Nice Sophia Antipolis, 2019).
Au pire, la recherche dichotomique examine $\lfloor \log_2 n \rfloor + 1$ éléments (la partie entière de $\log_2 n$, plus un) : $20$ pour un million d'éléments, car $2^{19} \le 10^6 < 2^{20}$. La base du logarithme ne compte pas dans un $O$ : $\log_2 n$ et $\log_{10} n$ ne diffèrent que d'un facteur constant.
Retiens l'ordre de croissance : $1$, $\log n$, $n$, $n \log n$, $n^2$, $2^n$, $n!$. Pour $n$ assez grand, chaque fonction devient négligeable devant la suivante, quelles que soient les constantes, et une puissance de $n$, même $n^{10}$, finit toujours sous $2^n$. Côté tris, la sélection et l'insertion coûtent $O(n^2)$ au pire, le tri fusion $O(n \log n)$ dans tous les cas, et le tri rapide, souvent plus rapide que le tri fusion en pratique, tombe à $O(n^2)$ au pire, quand le pivot coupe mal la liste (Lozes, 2019).
Définition : $f(n) = O(g(n))$ signifie qu'il existe une constante $c > 0$ et un rang $n_0$ tels que $f(n) \le c\,g(n)$ pour tout $n \ge n_0$. C'est une majoration : un algorithme en $O(n)$ est aussi en $O(n^2)$. Pour dire « exactement de cet ordre », on écrit $\Theta$ (grand thêta).
À retenir : si le temps est proportionnel à $n^2$, doubler $n$ multiplie le temps par $2^2 = 4$ ; s'il est proportionnel à $2^n$, ajouter $1$ à $n$ double le temps.
Piège classique : une ligne peut cacher une boucle. En Python, lire t[i] dans une liste coûte $O(1)$, mais le test x in t parcourt la liste et coûte $O(n)$ ; sur un ensemble (set), le même test coûte $O(1)$ en moyenne (wiki de python.org).
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Que coûte la lecture t[i] dans une liste Python t de taille $n$ ?
Réponse : C. Une liste Python est rangée dans un tableau : l'adresse de la case $i$ se calcule directement, quelle que soit la taille de la liste. Le piège D imagine qu'on avance case par case jusqu'à l'indice $i$, ce qui n'arrive qu'avec une liste chaînée (où chaque case pointe vers la suivante).
Question 2 : Une fonction contient for i in range(n): et, à l'intérieur, for j in range(n): avec une addition dans le corps. Quelle est sa complexité ?
Réponse : A. La boucle intérieure fait $n$ tours pour chacun des $n$ tours de la boucle extérieure : $n \times n = n^2$ additions. Le piège B additionne les deux boucles, alors qu'on additionne seulement quand elles se suivent.
Question 3 : Une fonction parcourt une liste de $n$ nombres pour trouver son minimum, puis, une fois cette boucle finie, la parcourt à nouveau pour compter les nombres pairs. Quelle est sa complexité ?
Réponse : D. Les deux boucles se suivent : $n + n = 2n$ tours, et la constante $2$ disparaît, d'où $O(n)$. Le piège A multiplie les deux boucles alors qu'aucune n'est dans l'autre.
Question 4 : Laquelle de ces fonctions finit par dépasser toutes les autres quand $n$ devient très grand ?
Réponse : B. Une exponentielle finit toujours par dépasser une puissance de $n$, quels que soient l'exposant et la constante. Le piège A est tentant, car $n^{10}$ reste devant pour les petites valeurs ($10^{10}$ contre $2^{10} = 1\,024$ pour $n = 10$), mais $2^n$ passe devant pour de bon dès $n = 59$.
Question 5 : Avec i = 1 au départ, combien de tours fait la boucle while i < n: i = 2 * i, en ordre de grandeur ?
Réponse : A. Après $k$ tours, $i = 2^k$ ; la boucle s'arrête dès que $2^k \ge n$, donc après environ $\log_2 n$ tours. Le piège B vaut pour i = i + 1 : ici $i$ double à chaque tour au lieu d'augmenter de $1$.
Question 6 : Lequel de ces tris garantit $O(n \log n)$ même dans le pire des cas ?
Réponse : C. Le tri fusion coupe toujours la liste en deux moitiés, à un élément près, puis les fusionne en temps linéaire, d'où $O(n \log n)$ dans tous les cas. Le piège A : le tri rapide est souvent plus rapide que le tri fusion en pratique, mais un pivot qui coupe mal à chaque étape, comme le premier élément d'une liste déjà triée, le fait tomber en $O(n^2)$.
Question 7 : Un programme dont le temps de calcul est proportionnel à $n^2$ met $2$ secondes pour $n = 10\,000$. Combien met-il pour $n = 20\,000$ ?
Réponse : B. $n$ est multiplié par $2$, donc le temps par $2^2 = 4$ : $2 \times 4 = 8$ secondes. Le piège A raisonne comme si le temps était proportionnel à $n$.
Question 8 : Dans for i in range(n):, la boucle intérieure est for j in range(i):, avec une comparaison dans son corps. Quelle est la complexité de ces deux boucles ?
Réponse : D. La boucle intérieure fait $0$, puis $1$, puis $2$ tours, jusqu'à $n - 1$ : au total $0 + 1 + \dots + (n-1) = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$ comparaisons, et on garde $n^2$ sans le facteur $\frac{1}{2}$. Le piège B croit qu'une boucle intérieure plus courte fait changer de classe, alors qu'elle ne fait gagner qu'un facteur constant.
Question 9 : Un programme dont le temps de calcul est proportionnel à $2^n$ met $1$ seconde pour $n = 30$. Combien met-il pour $n = 40$ ?
Réponse : A. Chaque unité ajoutée à $n$ double le temps : dix unités de plus le multiplient par $2^{10} = 1\,024$, soit $1\,024$ secondes, environ $17$ minutes. Le piège B applique une proportion, $\frac{40}{30} \approx 1{,}33$, qui ne vaut que pour un temps proportionnel à $n$.
Question 10 : Pour deux listes Python a et b de taille $n$, quelle est la complexité de la boucle for x in a: qui contient if x in b: c = c + 1 ?
Réponse : C. Le test x in b parcourt la liste b : jusqu'à $n$ comparaisons, pour chacun des $n$ éléments de a, soit $O(n^2)$. Le piège A ne compte que la boucle écrite ; en convertissant d'abord b en ensemble avec set(b), le test passerait à $O(1)$ en moyenne et le tout, conversion comprise, à $O(n)$.
Question 11 : Une recherche dichotomique examine l'élément du milieu, puis garde la moitié où la valeur peut se trouver. Sur une liste triée de $1\,024$ éléments, combien d'éléments examine-t-elle au maximum ?
Réponse : D. Au pire, la zone de recherche passe de $1\,024$ éléments à $512$, $256$, et ainsi de suite jusqu'à $2$, puis $1$ : onze tailles, donc onze éléments examinés, comme le donne $\lfloor \log_2 1024 \rfloor + 1 = 11$. Le piège A s'arrête à $\log_2 1024 = 10$ et oublie le dernier examen, quand il ne reste qu'un élément.
Question 12 : Un algorithme fait exactement $5n + 3$ opérations. Quelle affirmation est juste ?
Réponse : B. $O$ donne une majoration : pour $n \ge 3$, $5n + 3 \le 6n \le 6n^2$, donc l'algorithme est à la fois en $O(n)$ et en $O(n^2)$. Le piège A lit $O$ comme « exactement de l'ordre de », ce que dit $\Theta$ : cet algorithme est en $\Theta(n)$, pas en $\Theta(n^2)$.
Sources
Étienne Lozes, « Algorithmes de recherche et de tri », cours n°9 de programmation avec Python, L1 Sciences, Université Nice Sophia Antipolis, 2019.
Wiki de python.org, « TimeComplexity », coût des opérations sur les listes et les ensembles.