Analyse de Complexité et Efficacité Algorithmique

1. La hiérarchie des ordres de grandeur

Avant toute chose, il est crucial de visualiser ce que "plus efficace" signifie. Quand on dit qu'un algorithme en $O(n\log n)$ est meilleur qu'un autre en $O(n^2)$, la différence n'est pas marginale, elle est colossale à mesure que la taille de l'entrée $n$ augmente.

Le graphique ci-dessous illustre cette divergence de manière frappante.

Intuitivement, on peut classer les fonctions de complexité usuelles dans une hiérarchie, de la plus efficace (croissance la plus lente) à la moins efficace (croissance la plus rapide) :

1. Constant : $\Theta (1)$
2. Logarithmique : $\Theta (\log n)$
3. Linéaire : $\Theta (n)$
4. Linéarithmique : $\Theta (n\log n)$
5. Polynomial : $\Theta (n^k)$ (avec $k>1$, ex: $\Theta (n^2)$, $\Theta (n^3)$)
6. Exponentiel : $\Theta (k^n)$ (avec $k>1$, ex: $\Theta (2^n)$)
7. Factoriel : $\Theta (n!)$

Cette hiérarchie est votre première ligne d'analyse. Si l'algorithme A a une complexité $T_A(n)$ qui se situe plus bas dans cette hiérarchie que la complexité $T_B(n)$ de l'algorithme B, alors A est asymptotiquement plus efficace.

2. Une méthode pratique de comparaison

Pour la plupart des complexités que vous rencontrerez, qui sont souvent une combinaison de termes polynomiaux, logarithmiques et parfois exponentiels, il existe une règle de comparaison systématique.

La vidéo suivante expose cette méthode de manière claire et directe.

Pour résumer la méthode vue dans la vidéo, si vous devez comparer deux fonctions de complexité $C_1(n)=n^{{\alpha }_1}(\log n{)}^{{\beta }_1}{\gamma }_1^n$ et $C_2(n)=n^{{\alpha }_2}(\log n{)}^{{\beta }_2}{\gamma }_2^n$, procédez comme suit :

1. Comparez les bases exponentielles ($\gamma$) : Si ${\gamma }_1>{\gamma }_2$, alors $C_1$ croît plus vite que $C_2$. Le facteur exponentiel domine tout le reste.
2. Si les bases exponentielles sont égales, comparez les exposants polynomiaux ($\alpha$) : Si ${\alpha }_1>{\alpha }_2$, alors $C_1$ croît plus vite.
3. Si les exposants polynomiaux sont aussi égaux, comparez les exposants logarithmiques ($\beta$) : Si ${\beta }_1>{\beta }_2$, alors $C_1$ croît plus vite.

Cette méthode est un outil pragmatique et rapide, très utile en situation d'examen.

3. La justification formelle par les limites

La méthode précédente est excellente, mais pour une justification mathématique irréfutable, et pour traiter des cas plus généraux, l'outil de choix est l'étude de la limite du rapport des deux fonctions de complexité.

Soient deux algorithmes A et B avec des complexités respectives $f(n)$ et $g(n)$. Pour les comparer, on étudie :
$L={\lim }_{n\to \infty }\frac{f(n)}{g(n)}$

L'interprétation de la valeur de $L$ nous dit tout sur la relation asymptotique entre $f$ et $g$ :

1. Si $L=0$ : $g(n)$ croît beaucoup plus vite que $f(n)$. On dit que $f(n)$ est asymptotiquement plus petit que $g(n)$. L'algorithme A est plus efficace que B. Formellement, on note $f(n)=o(g(n))$ ("petit o").

2. Si $L=c$, où $c$ est une constante finie et positive ($0<c<\infty$) : $f(n)$ et $g(n)$ croissent à la même vitesse. Leurs algorithmes respectifs ont la même classe de complexité asymptotique. Formellement, on note $f(n)=\Theta (g(n))$.

3. Si $L=\infty$ : $f(n)$ croît beaucoup plus vite que $g(n)$. On dit que $f(n)$ est asymptotiquement plus grand que $g(n)$. L'algorithme B est plus efficace que A. Formellement, on note $f(n)=\omega (g(n))$ ("petit oméga").

Le document suivant (en anglais, mais d'une grande clarté conceptuelle) détaille cette approche et la relie aux notations asymptotiques, y compris les notations "strictes" o et ω qui sont essentielles pour une comparaison formelle.

4. Mise en pratique : étude de cas

Appliquons cette méthode formelle pour comparer deux algorithmes d'exponentiation modulaire, qui calculent $a^b(\mathrm{mod}N)$. C'est un exemple classique et très important, notamment en cryptographie.

Algorithme 1 : Exponentiation naïve
L'idée est simple : on multiplie a par lui-même b-1 fois, en prenant le modulo à chaque étape.

fonction puissance_naive(a, b, N)
  res = 1
  pour i de 1 à b:
    res = (res * a) % N
  retourner res

Chaque multiplication modulaire de grands nombres a un coût, disons en $O((\log N{)}^2)$. Comme on effectue $b$ multiplications, la complexité totale est $T_{naif}(b)=O(b\cdot (\log N{)}^2)$.

Algorithme 2 : Exponentiation rapide (binaire)
Cette méthode, plus astucieuse, utilise la décomposition binaire de l'exposant b. Le nombre de multiplications est proportionnel au nombre de bits de b, c'est-à-dire ${\log }_{2}b$. La complexité est donc $T_{rapide}(b)=O(\log b\cdot (\log N{)}^2)$.
(Le détail de ces analyses de complexité est présenté dans les sections 2.2 et 2.2 du document LINK que nous utiliserons plus tard.)

Comparaison formelle :
Nous devons comparer $f(b)=b$ et $g(b)=\log b$. (Le terme $(\log N{)}^2$ est une constante par rapport à b).

Utilisons la méthode des limites :
$L={\lim }_{b\to \infty }\frac{g(b)}{f(b)}={\lim }_{b\to \infty }\frac{\log b}{b}$
C'est une forme indéterminée $\infty /\infty$. Nous pouvons utiliser la règle de L'Hôpital (vue dans la ressource LINK, section "Limit rules") :
$L={\lim }_{b\to \infty }\frac{(\log b{)}^{\prime }}{(b{)}^{\prime }}={\lim }_{b\to \infty }\frac{1/b}{1}={\lim }_{b\to \infty }\frac{1}{b}=0$

Conclusion :
Puisque la limite est 0, nous avons $\log b=o(b)$. Cela signifie que la complexité de l'exponentiation rapide, $O(\log b\cdot (\log N{)}^2)$, est asymptotiquement bien meilleure que celle de l'exponentiation naïve, $O(b\cdot (\log N{)}^2)$. Le gain est exponentiel !

5. Exercices d'entraînement

Pour chaque paire de fonctions $f(n)$ et $g(n)$ ci-dessous, déterminez si $f(n)=o(g(n))$, $f(n)=\omega (g(n))$ ou $f(n)=\Theta (g(n))$. Justifiez votre réponse par un calcul de limite.

1. $f(n)=100n^2$, $g(n)=0.5n^3$
2. $f(n)=n{\log }_{2}n$, $g(n)=n^{\sqrt{2}}$
3. $f(n)=n^{{\log }_{2}7}$ (complexité de Strassen), $g(n)=n^3$ (complexité de la multiplication matricielle naïve)
4. $f(n)=\sqrt{n}$, $g(n)=(\log n{)}^5$
5. $f(n)=2^n$, $g(n)=3^{n/2}$

Solutions

1. ${\lim }_{n\to \infty }\frac{100n^2}{0.5n^3}={\lim }_{n\to \infty }\frac{200}{n}=0$. Donc, $f(n)=o(g(n))$.
2. ${\lim }_{n\to \infty }\frac{n{\log }_{2}n}{n^{\sqrt{2}}}={\lim }_{n\to \infty }\frac{{\log }_{2}n}{n^{\sqrt{2}-1}}$. Comme $\sqrt{2}-1\approx 0.41>0$, le polynôme l'emporte sur le logarithme. La limite est 0. Donc, $f(n)=o(g(n))$.
3. ${\log }_{2}7\approx 2.807$. ${\lim }_{n\to \infty }\frac{n^{2.807}}{n^3}={\lim }_{n\to \infty }\frac{1}{n^{0.193}}=0$. L'algorithme de Strassen est bien asymptotiquement plus efficace. $f(n)=o(g(n))$.
4. ${\lim }_{n\to \infty }\frac{(\log n{)}^5}{\sqrt{n}}={\lim }_{n\to \infty }\frac{(\log n{)}^5}{n^{0.5}}$. Toute puissance de $\log n$ croît moins vite que toute puissance positive de $n$. La limite est 0. Donc, $g(n)=o(f(n))$, ce qui équivaut à $f(n)=\omega (g(n))$.
5. $3^{n/2}=(\sqrt{3}{)}^n\approx (1.732{)}^n$. On compare $2^n$ et $(1.732{)}^n$. ${\lim }_{n\to \infty }\frac{(1.732{)}^n}{2^n}={\lim }_{n\to \infty }(\frac{1.732}{2}{)}^n=0$, car la base est $<1$. Donc, $g(n)=o(f(n))$, ou $f(n)=\omega (g(n))$.

Conclusion de la leçon et du module

Cette leçon achève notre premier module sur les fondements de l'analyse d'algorithmes. Vous êtes maintenant équipé pour non seulement calculer, mais aussi comparer formellement l'efficacité des algorithmes, une compétence absolument centrale pour l'Agrégation.

Points clés à retenir :

• La hiérarchie des fonctions de complexité (log, linéaire, polynomial, etc.) donne un premier ordre de comparaison rapide.
• Pour les fonctions de type $n^{\alpha }(\log n{)}^{\beta }{\gamma }^n$, la règle exponentiel > polynomial > logarithmique est une méthode pratique et efficace.
• La méthode la plus rigoureuse est le calcul de la limite du rapport ${\lim }_{n\to \infty }f(n)/g(n)$. Sa valeur (0, une constante positive, ou l'infini) détermine la relation asymptotique.
• Les notations $o$ et $\omega$ sont utilisées pour les comparaisons strictes, indiquant qu'un algorithme est définitivement "meilleur" ou "moins bon" qu'un autre.

Dans le prochain module, "Structures de Données Linéaires et Hachage", nous allons commencer à construire l'arsenal des structures de données fondamentales : piles, files, listes chaînées, etc. Pour chaque structure et chaque opération, nous appliquerons systématiquement les techniques d'analyse que vous venez d'apprendre pour en évaluer la performance. La théorie que nous avons établie devient maintenant notre principal outil pratique.