Optimisation d'algorithmes : techniques de tri

1. Le principe de l'optimisation : un coût pour un gain

L'optimisation en algorithmique est souvent une histoire de compromis. L'idée est d'effectuer une opération de "pré-traitement" sur les données. Cette opération a un coût, mais elle permet ensuite d'exécuter l'algorithme principal de manière beaucoup plus efficace.

La stratégie est gagnante si :

Coût du pré-traitement + Coût du nouvel algorithme < Coût de l'algorithme par force brute

La technique de pré-traitement la plus courante et la plus puissante est le tri. Trier une liste de données nous permet d'exploiter l'ordre des éléments pour éviter des opérations inutiles.

Le document ci-dessous illustre parfaitement ce principe.

Comme vous l'avez lu, si une liste est déjà triée, trouver le maximum devient une opération instantanée (complexité $O(1)$) au lieu de devoir parcourir toute la liste (complexité $O(n)$).

Cependant, la liste n'est généralement pas triée au départ. Le véritable gain apparaît lorsque le coût du tri est largement compensé par l'efficacité du nouvel algorithme qu'il autorise. Voyons cela avec l'exemple le plus classique : la recherche d'un élément.

2. Cas d'étude : Recherche d'un élément

Imaginons que nous devons chercher un élément dans un tableau.

• Approche par force brute : la recherche séquentielle
  Comme son nom l'indique, on parcourt le tableau élément par élément jusqu'à trouver celui qu'on cherche ou arriver à la fin. Dans le pire des cas, il faut vérifier tous les éléments. La complexité est donc linéaire, $O(n)$.

• Approche optimisée : le tri suivi de la recherche dichotomique
  Cette approche se fait en deux temps :

  1. Pré-traitement : On trie le tableau.
  2. Algorithme optimisé : On utilise la recherche dichotomique (binaire), qui exploite l'ordre pour éliminer la moitié des éléments restants à chaque étape.

Pour comprendre la différence fondamentale entre ces deux méthodes de recherche, l'article suivant est très éclairant.

Analyse de la performance

Analysons le coût de l'approche optimisée :

1. Coût du tri : Un algorithme de tri efficace, comme le tri fusion ou le tri rapide, a une complexité moyenne de $O(n\log n)$.
2. Coût de la recherche dichotomique : Comme vous l'avez lu, sa complexité est $O(\log n)$.

Le coût total est donc $O(n\log n)+O(\log n)$, ce qui se simplifie en $O(n\log n)$.

Si vous ne faites qu'une seule recherche, passer de $O(n)$ à $O(n\log n)$ n'est pas forcément un gain. Mais le tri devient extrêmement rentable si :

• Vous devez effectuer de nombreuses recherches dans le même tableau.
• L'algorithme que vous cherchez à optimiser est bien plus coûteux, comme un algorithme en $O(n^2)$.

3. Application : Optimiser le problème de la somme de deux nombres

Rappelez-vous du problème de la leçon précédente :

Étant donné un tableau T de n nombres et un nombre cible S, existe-t-il deux nombres dans le tableau dont la somme est égale à S ?

La solution par force brute consistait à tester toutes les paires possibles avec deux boucles imbriquées, pour une complexité de $O(n^2)$.

Appliquons notre technique d'optimisation :

1. Pré-traitement : On trie le tableau T. Coût : $O(n\log n)$.

2. Algorithme optimisé : la technique des deux pointeurs.
   Une fois le tableau trié, on peut utiliser une méthode très astucieuse. On place un pointeur gauche au tout début du tableau et un pointeur droite à la toute fin.

   Algorithme TrouverSommeOptimise(T, S)
     Trier(T)  // Étape 1 : Coût O(n log n)
   
     gauche <- 0
     droite <- longueur(T) - 1
   
     Tant que gauche < droite
       somme_actuelle <- T[gauche] + T[droite]
   
       Si somme_actuelle = S
         Retourner Vrai  // On a trouvé !
   
       Sinon Si somme_actuelle < S
         // La somme est trop petite, il faut l'augmenter.
         // On déplace le pointeur gauche vers un plus grand nombre.
         gauche <- gauche + 1
   
       Sinon // somme_actuelle > S
         // La somme est trop grande, il faut la diminuer.
         // On déplace le pointeur droite vers un plus petit nombre.
         droite <- droite - 1
   
     Retourner Faux // On a parcouru tout le tableau sans trouver de solution
   

Analyse de la performance

• Coût du tri : $O(n\log n)$.
• Coût de la boucle Tant que : Dans le pire des cas, les pointeurs gauche et droite se croisent après avoir parcouru l'ensemble du tableau une seule fois. Cette partie de l'algorithme a donc une complexité linéaire, $O(n)$.

Le coût total est $O(n\log n)+O(n)$, ce qui se simplifie en $O(n\log n)$.

Conclusion : Nous avons transformé un algorithme quadratique $O(n^2)$ en un algorithme quasi-linéaire $O(n\log n)$. Pour un tableau d'un million d'éléments, cela représente la différence entre des milliers de milliards d'opérations et seulement quelques millions. Le gain est spectaculaire !

4. Le coût du tri

Nous avons vu que le tri est la clé, mais il n'est pas gratuit. Il est important de savoir qu'il existe de nombreux algorithmes de tri, avec des performances très différentes.

L'image ci-dessous compare visuellement deux approches pour trier : le tri à bulles (simple mais lent) et le tri rapide (plus complexe mais efficace).

Le choix de l'algorithme de tri est donc important. Heureusement, comme le souligne la ressource suivante, il est rare d'avoir à les implémenter soi-même.

Conclusion

Aujourd'hui, vous avez découvert l'une des stratégies d'optimisation les plus fondamentales en algorithmique. Une solution par force brute est un bon début, mais une analyse plus poussée révèle souvent des opportunités d'amélioration spectaculaires.

Points clés à retenir :

• L'optimisation consiste souvent à investir dans un pré-traitement (comme le tri) pour rendre l'algorithme principal beaucoup plus rapide.
• Le tri préalable des données est une technique extrêmement puissante. Il permet de passer de recherches séquentielles ($O(n)$) à des recherches dichotomiques ($O(\log n)$).
• Cette technique peut transformer des algorithmes lents, comme une recherche de paires en $O(n^2)$, en solutions très efficaces en $O(n\log n)$ grâce à des méthodes comme celle des deux pointeurs.
• Le coût du tri ($O(n\log n)$ pour un bon algorithme) est le facteur qui détermine la complexité finale de la solution optimisée.

Dans notre prochaine leçon, nous conclurons ce module en analysant le gain de complexité que nous obtenons après avoir optimisé un algorithme, afin de quantifier précisément l'amélioration de performance réalisée.