Optimisation algorithmique : gain en complexité.

1. Du théorique au concret : l'impact de la complexité

Jusqu'à présent, nous avons manipulé des notations comme $O(n)$, $O(n^2)$ ou $O(n\log n)$. Mais que représentent-elles concrètement ? Ces notations décrivent la courbe de croissance du temps d'exécution d'un algorithme lorsque la taille des données d'entrée (n) augmente.

Observemos le graphique suivant :

Comme vous pouvez le constater, une complexité quadratique ($O(n^2)$) augmente de façon spectaculaire par rapport à une complexité quasi-linéaire ($O(n\log n)$). Mais que cela signifie-t-il en termes de temps ?

Le tableau ci-dessous traduit ces courbes en temps de calcul approximatifs. C'est ici que le gain d'une optimisation devient tangible.

Analyser ce tableau nous permet de tirer une conclusion fondamentale :

• Pour $n=10$, la différence est négligeable.
• Pour $n=100000$, un algorithme en $O(n^2)$ prendrait plus de 2 heures, alors qu'un algorithme en $O(n\log n)$ s'exécute en moins d'une seconde.
• Pour $n=1000000$, la différence se mesure en jours contre quelques millisecondes.

Le "gain" que nous analysons est donc un gain en scalabilité : la capacité de votre algorithme à gérer de grandes quantités de données dans un temps raisonnable. Dans la leçon précédente, en passant de $O(n^2)$ à $O(n\log n)$, vous n'avez pas juste "amélioré" l'algorithme, vous l'avez fait passer de "inutilisable pour de grosses données" à "très efficace".

2. Étude de cas : Le gain exponentiel du "Diviser pour Régner"

Voyons un exemple classique où le gain est encore plus spectaculaire.

Problème : Calculer la puissance d'un nombre, soit $x^n$.

• Solution "brute-force" : Il suffit de multiplier x par lui-même n-1 fois à l'aide d'une boucle.

  Algorithme PuissanceNaive(x, n)
    resultat <- 1
    Pour i de 1 à n
      resultat <- resultat * x
    Retourner resultat
  

  L'analyse est simple : la boucle s'exécute n fois. La complexité est donc linéaire, $O(n)$.

• Solution optimisée (exponentiation rapide) : On peut utiliser une approche "diviser pour régner".

  • Si n est pair, alors $x^n=(x^{n/2}{)}^2$. On calcule $x^{n/2}$ une seule fois et on met le résultat au carré.
  • Si n est impair, alors $x^n=x\cdot x^{n-1}=x\cdot (x^{(n-1)/2}{)}^2$.

  À chaque étape, on divise le problème par deux. Ce mécanisme de division répétée est la marque d'une complexité logarithmique. La complexité est en $O(\log n)$.

Analyse du gain

Nous passons d'une complexité linéaire $O(n)$ à une complexité logarithmique $O(\log n)$.
Reportons-nous au tableau :

• Pour calculer $x^{1000000}$, la méthode naïve nécessite un million de multiplications.
• La méthode optimisée nécessite environ 20 multiplications (${\log }_2(1000000)\approx 19.96$).

Le gain est colossal. Nous avons transformé un problème qui pouvait être lent pour de grands n en un problème quasi-instantané, quelle que soit la taille de n. Le document suivant présente ce problème et d'autres exemples d'optimisation.

3. Étude de cas : Le gain par pré-calcul

Parfois, l'optimisation ne vient pas d'un algorithme plus malin, mais d'un investissement initial : le pré-calcul.

Problème : On nous donne une matrice (tableau à 2 dimensions). On doit répondre à de nombreuses requêtes demandant la somme des éléments d'une sous-matrice rectangulaire.

• Solution "brute-force" : Pour chaque requête, on parcourt la sous-matrice demandée avec deux boucles imbriquées et on additionne les éléments.

  • Si la sous-matrice a pour taille h (hauteur) et w (largeur), la complexité pour une seule requête est de $O(h\times w)$.
  • Si on doit répondre à k requêtes, la complexité totale peut devenir très élevée.

• Solution optimisée (table des sommes cumulées) :

  1. Pré-calcul : On crée une seconde matrice, de même taille, appelée "table de sommation". Pour chaque case (i, j), on stocke la somme de tous les éléments du rectangle allant de l'origine (0, 0) à (i, j). Ce pré-calcul se fait une seule fois, en parcourant la matrice originale. Coût : $O(\text{N}\times \text{M})$, où N et M sont les dimensions de la matrice.
  2. Requête : Grâce à cette table, la somme de n'importe quel rectangle peut être calculée en seulement 4 accès à la table et quelques additions/soustractions. Le calcul devient indépendant de la taille du rectangle. Coût par requête : $O(1)$, soit un temps constant !

Analyse du gain

Nous avons un compromis :

• Un coût initial de $O(N\times M)$ pour construire la table.
• Un gain immense pour chaque requête suivante : on passe de $O(h\times w)$ à $O(1)$.

Cette optimisation est extrêmement rentable si le nombre de requêtes est élevé. C'est un schéma classique en informatique : investir du temps et de la mémoire en amont pour accélérer considérablement les opérations futures.

Vous pouvez retrouver ce problème dans les exercices 6 et 7 du même document, "Optimisation des Algorithmes".

4. Du pire au meilleur : l'exemple de Fibonacci

Pour finir, analysons un cas où l'on peut appliquer plusieurs niveaux d'optimisation, avec des gains spectaculaires à chaque étape.

Problème : Calculer le n-ième terme de la suite de Fibonacci.

Le document suivant analyse en détail la complexité de trois approches pour résoudre ce problème. C'est un cas d'école pour comprendre l'analyse de gain.

Analyse des gains successifs

Résumons les gains que vous avez découverts dans ce document :

1. Solution 1 : Récursive naïve

   • Complexité : $O(2^n)$ (exponentielle).
   • Performance : Devient inutilisable très rapidement (pour n > 40). C'est une solution "intractable".

2. Solution 2 : Itérative (avec une boucle)

   • Complexité : $O(n)$ (linéaire).
   • Gain 1 -> 2 : On passe d'une complexité exponentielle à une complexité polynomiale (linéaire). C'est le gain le plus important, celui qui rend l'algorithme utilisable en pratique. C'est la différence entre des années de calcul et une fraction de seconde.

3. Solution 3 : Matricielle (exponentiation rapide)

   • Complexité : $O(\log n)$ (logarithmique).
   • Gain 2 -> 3 : On passe de linéaire à logarithmique. L'algorithme devient quasi-instantané même pour des valeurs de n immenses (des milliers ou des millions), pour lesquelles la version itérative commencerait à prendre un temps mesurable.

Cet exemple montre qu'analyser le gain en complexité, c'est identifier le passage d'une "classe de complexité" à une autre, et comprendre l'impact concret que cela aura sur l'utilisabilité de votre programme.

Conclusion

Vous voilà au terme de ce module. Vous avez appris non seulement à identifier des solutions "brute-force" et à les optimiser, mais aussi, aujourd'hui, à mesurer et à justifier l'intérêt de ces optimisations.

Points clés à retenir :

• Analyser le gain en complexité, c'est comparer les classes de complexité (ex: $O(n^2)$ vs $O(n\log n)$) de la solution initiale et de la solution optimisée.
• Ce gain se traduit par une meilleure scalabilité : la capacité de l'algorithme à traiter de grands volumes de données dans un temps raisonnable.
• Les gains les plus importants sont ceux qui font passer un algorithme d'une classe de complexité élevée (exponentielle, polynomiale d'ordre élevé) à une classe plus basse (linéaire, logarithmique).
• L'optimisation peut passer par un algorithme plus intelligent (diviser pour régner) ou par un pré-calcul qui amortit son coût sur de nombreuses utilisations futures.

Cette compétence est la dernière pièce du puzzle avant de vous lancer dans un projet complet. Vous êtes maintenant capable d'analyser un problème, de concevoir une solution, de l'optimiser, et d'expliquer pourquoi votre nouvelle solution est meilleure.

La prochaine et dernière étape de votre parcours sur les algorithmes sera le Projet de Synthèse, où vous mettrez en pratique tout ce que vous avez appris, de la définition d'un algorithme à l'analyse de son efficacité. Félicitations pour le chemin parcouru