Comprendre la complexité temporelle et spatiale des algorithmes aide à évaluer leur efficacité. Tri fusion et tri rapide sont deux algorithmes de tri populaires avec des caractéristiques de performance différentes. Cet article explique comment calculer leurs complexités.

Fusionner la complexité de tri

Fusionner le tri divise le tableau en deux moitiés récursivement jusqu'à ce que chaque sous-array contienne un seul élément. Le processus de fusion combine ensuite ces sous-arrays dans l'ordre trié.

La complexité temporelle du tri de fusion est O(n log n) dans les meilleurs cas, moyens et pires, car il divise systématiquement le tableau et le fusionne efficacement.

La complexité de l'espace est O(n) en raison du besoin de tableaux temporaires pendant le processus de fusion.

Complexité de tri rapide

Le tri rapide sélectionne un élément pivot et partitionne le tableau en sous-arrachages qui sont inférieurs ou supérieurs au pivot. Ce processus est répété de façon récursive.

La complexité temporelle moyenne est O(n log n), mais dans le pire des cas, comme lorsque l'élément le plus petit ou le plus grand est toujours choisi comme pivot, il se dégrade en O(n^2).

La complexité de l'espace pour le tri rapide est généralement O(log n) en raison de l'espace de la pile récursive, mais il peut être plus élevé selon l'implémentation.

Résumé des complexités

  • Tri de fusion - Heure : O(n log n), Espace : O(n)
  • Tri rapide - Heure : Moyenne O(n log n), Pire O(n^2), Espace : O(log n)