Analyse de la complexité algorithmique

Que signifie $f(n)=O(g(n))$ ?

La notation $O$ exprime une majoration asymptotique à une constante multiplicative près, valable seulement à partir d'un certain rang $n_0$ (le comportement pour les petites valeurs de $n$ n'a pas d'importance).

Vrai ou faux : un algorithme de complexité $O(n\log n)$ est, pour $n$ grand, plus rapide qu'un algorithme de complexité $O(n^2)$.

Vrai. La fonction $n\log n$ croît strictement plus lentement que $n^2$ pour $n$ assez grand (le rapport $n^2/(n\log n)=n/\log n\to+\infty$), donc un algorithme $O(n\log n)$ devient toujours plus rapide qu'un $O(n^2)$ au-delà d'un certain seuil.

Quelle est la complexité d'une boucle simple parcourant un tableau de taille $n$ une seule fois ?

Une boucle qui exécute une opération constante pour chacun des $n$ éléments du tableau coûte $O(n)$ : un nombre d'opérations proportionnel à la taille de l'entrée.

Vrai ou faux : la recherche dichotomique dans un tableau trié de taille $n$ a une complexité $O(\log n)$.

Vrai. À chaque étape, la dichotomie divise par deux la taille de l'espace de recherche, donc le nombre d'étapes nécessaires pour atteindre une taille $1$ est $\log_2 n$.

Quelle est la complexité, dans le pire cas, du tri rapide (quicksort) ?

Dans le pire cas (pivot systématiquement mal choisi), le tri rapide se dégrade en $O(n^2)$, bien que sa complexité moyenne soit $O(n\log n)$ avec un bon choix de pivot.

Montrer que $f(n)=5n^3+2n^2+n$ est $\Theta(n^3)$.

Pour $n\geq1$ : $5n^3+2n^2+n\leq5n^3+2n^3+n^3=8n^3$ (majoration, $O(n^3)$) et $5n^3+2n^2+n\geq5n^3$ (minoration, $\Omega(n^3)$). Les deux bornes étant vérifiées, $f(n)=\Theta(n^3)$.

À l'aide du théorème maître avec $a=2,b=2,f(n)=\Theta(n)$ (cas $d=1$), quelle est la complexité du tri fusion ?

$p=\log_2 2=1=d$, donc on est dans le cas $d=p$ du théorème maître : $T(n)=\Theta(n^p\log n)=\Theta(n\log n)$.

Pour deux boucles imbriquées, la première parcourant $n$ éléments et la seconde (à l'intérieur) parcourant $n$ éléments également, quelle est la complexité totale ?

Pour chacune des $n$ itérations de la boucle externe, la boucle interne s'exécute $n$ fois, donc le nombre total d'opérations est $n\times n=n^2$, soit $O(n^2)$.

Vrai ou faux : la complexité dans le pire cas est toujours supérieure ou égale à la complexité en moyenne.

Vrai. La complexité en moyenne est une espérance sur toutes les entrées possibles de taille $n$, qui ne peut pas dépasser la valeur maximale (le pire cas) atteinte par cette même quantité.

Pourquoi le calcul naïf (double récursion sans mémoïsation) de Fibonacci a-t-il une complexité exponentielle, alors que la suite elle-même se calcule en $O(n)$ avec une boucle ?

Le problème : redondance des calculs. L'appel récursif $\text{Fib}(n)=\text{Fib}(n-1)+\text{Fib}(n-2)$ génère un arbre d'appels où chaque sous-problème $\text{Fib}(k)$ pour $k<n$ est recalculé un grand nombre de fois — par exemple, $\text{Fib}(n-2)$ est appelé à la fois directement (par $\text{Fib}(n)$) et indirectement (via $\text{Fib}(n-1)\to\text{Fib}(n-2)$). Le nombre total d'appels suit la récurrence $T(n)=T(n-1)+T(n-2)+O(1)$, dont la solution est $\Theta(\varphi^n)$ ($\varphi\approx1{,}618$) — une croissance exponentielle.

La solution : éviter la redondance. Une approche itérative (ou récursive avec mémoïsation) calcule chaque valeur $\text{Fib}(k)$ une seule fois, en la stockant pour réutilisation ultérieure. En ne gardant en mémoire que les deux derniers termes calculés et en itérant de $0$ à $n$, on obtient un algorithme en $O(n)$ — chaque valeur intermédiaire est calculée et utilisée immédiatement, sans recalcul.

C'est l'illustration la plus simple du principe de la programmation dynamique : transformer une récursion exponentielle redondante en un calcul polynomial en éliminant les recalculs de sous-problèmes identiques.

Démontrer, en utilisant le théorème maître, que la recherche dichotomique dans un tableau trié de taille $n$ a une complexité $\Theta(\log n)$.

Mise en équation. À chaque étape de la dichotomie, on compare l'élément cherché à l'élément central du tableau (coût constant $\Theta(1)$), puis on poursuit la recherche dans une seule des deux moitiés (donc $a=1$ sous-problème), de taille $n/2$ (donc $b=2$). La récurrence est :

Application du théorème maître. On identifie $f(n)=\Theta(n^d)$ avec $d=0$ (coût constant). On calcule $p=\log_b a=\log_2 1=0$.

Comme $d=0=p$, on est dans le cas $d=p$ du théorème maître, qui donne $T(n)=\Theta(n^p\log n)=\Theta(n^0\log n)=\Theta(\log n)$.

Conclusion : la recherche dichotomique est $\Theta(\log n)$. $\square$ C'est cohérent avec l'intuition : la taille de l'intervalle de recherche est divisée par $2$ à chaque étape, donc il faut $\log_2 n$ étapes pour atteindre une taille $1$.

Un algorithme a la récurrence $T(n)=4T(n/2)+\Theta(n)$. Déterminer sa complexité via le théorème maître, et donner un exemple classique d'algorithme suivant cette récurrence.

Identification des paramètres. Dans $T(n)=4T(n/2)+\Theta(n)$ : $a=4$ sous-problèmes, $b=2$ (chacun de taille $n/2$), et $f(n)=\Theta(n)=\Theta(n^d)$ avec $d=1$.

Calcul de $p$. $p=\log_b a=\log_2 4=2$.

Comparaison $d$ vs $p$. Comme $d=1<p=2$, on est dans le cas $d<p$ du théorème maître, qui donne :

Exemple classique. Cette récurrence est typique de l'algorithme naïf de multiplication de matrices carrées par blocs récursifs : pour multiplier deux matrices $n\times n$ découpées en 4 blocs $(n/2)\times(n/2)$, la formule par blocs nécessite $8$ multiplications récursives de matrices de taille $n/2$ dans la version la plus naïve (et $\Theta(n^2)$ pour les additions de blocs) — donnant en fait $T(n)=8T(n/2)+\Theta(n^2)$, soit $\Theta(n^3)$ (la complexité usuelle, non optimisée, de la multiplication matricielle). Une version simplifiée à $4$ sous-appels correspondrait plutôt à un algorithme hypothétique de coût linéaire de combinaison, illustrant ici purement le mécanisme du théorème maître.

Vrai ou faux : $2^n=O(n^{100})$.

Faux. Toute fonction exponentielle $2^n$ croît, à terme, strictement plus vite que n'importe quel polynôme $n^k$ (quel que soit $k$ fixé, même très grand comme $100$) : $\lim_{n\to+\infty}2^n/n^{100}=+\infty$. C'est un résultat classique d'analyse asymptotique (croissance exponentielle l'emporte toujours sur la croissance polynomiale).

Démontrer que $\log(n!)=\Theta(n\log n)$ (formule utile pour analyser la complexité optimale du tri, via la formule de Stirling $n!\sim\sqrt{2\pi n}\,(n/e)^n$).

Formule de Stirling. $n!\sim\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n$ quand $n\to+\infty$, donc en prenant le logarithme :

Identification du terme dominant. Le terme $n\ln n$ domine strictement les deux autres ($-n=O(n)=o(n\ln n)$ et $\frac12\ln(2\pi n)=O(\log n)=o(n\ln n)$), donc :

Conclusion. Comme $\log$ et $\ln$ diffèrent d'un facteur multiplicatif constant ($\log_2 x=\ln x/\ln2$), on a aussi $\log(n!)=\Theta(n\log n)$. $\square$ Ce résultat est la base de la preuve que tout algorithme de tri par comparaisons a une complexité $\Omega(n\log n)$ dans le pire cas (il y a $n!$ permutations possibles à distinguer, donc il faut au moins $\log_2(n!)=\Theta(n\log n)$ comparaisons pour les départager) — ce qui montre que le tri fusion, avec sa complexité $\Theta(n\log n)$, est optimal parmi les algorithmes de tri par comparaisons.

On considère l'algorithme récursif de calcul de $x^n$ par exponentiation rapide : $x^n=(x^{n/2})^2$ si $n$ pair, $x^n=x\cdot(x^{(n-1)/2})^2$ si $n$ impair. Établir sa complexité en nombre de multiplications.

Mise en équation. À chaque appel récursif, on réduit le problème de taille $n$ à un seul sous-problème de taille $n/2$ (calculer $x^{n/2}$ ou $x^{(n-1)/2}$), suivi d'un nombre constant d'opérations supplémentaires (une mise au carré, et éventuellement une multiplication par $x$ si $n$ est impair). La récurrence est :

Application du théorème maître. $a=1$, $b=2$, $d=0$ (coût constant de combinaison). $p=\log_2 1=0=d$, donc on est dans le cas $d=p$ :

Comparaison avec la méthode naïve. Le calcul naïf de $x^n$ par multiplications successives ($x\times x\times\cdots\times x$, $n-1$ fois) coûte $\Theta(n)$ multiplications. L'exponentiation rapide ne nécessite que $\Theta(\log n)$ multiplications — un gain exponentiel en pratique (par exemple, calculer $x^{1\,000\,000}$ demande environ $20$ multiplications au lieu d'un million). Cette technique est à la base de nombreux algorithmes cryptographiques modernes (exponentiation modulaire RSA, etc.).