Quelle est la complexité du tri fusion dans le pire cas ?
Réponse courte
Le tri fusion équilibré a une complexité temporelle O(n log n) dans le pire cas, où n est le nombre de valeurs. À chaque niveau, les fusions traitent au total n éléments et il y a environ log₂(n) niveaux.
Comprendre
Le travail d’un niveau
Le tri fusion divise une liste en sous-listes jusqu’à obtenir des listes de zéro ou un élément. Il les combine ensuite par fusion. Fusionner deux listes déjà triées contenant au total n valeurs demande un travail proportionnel à n : chaque valeur est copiée et les têtes sont comparées au fil de l’opération.
Compter les niveaux
Quand les divisions sont équilibrées, la taille est approximativement divisée par deux à chaque niveau. Il faut environ log₂(n) divisions pour atteindre des listes unitaires. Par exemple, pour n = 8, il y a 3 niveaux de fusion, car 2³ = 8. À chacun, les fusions traitent ensemble 8 valeurs.
En déduire la complexité
Le travail est donc de l’ordre de n par niveau, répété sur environ log₂(n) niveaux, soit O(n log n). Cette borne reste vraie dans le pire cas pour le tri fusion équilibré, y compris quand la liste initiale est dans un ordre défavorable. O(n log n) décrit un ordre de croissance, pas un temps mesuré en secondes ni un nombre exact de comparaisons.
Ne compter qu’une dimension est trompeur
La profondeur récursive est logarithmique, mais cela ne rend pas le tri complet O(log n) : chaque niveau traite au total les n valeurs. La version qui crée des listes intermédiaires utilise aussi un espace auxiliaire O(n), distinction à garder séparée de la complexité temporelle.
Étapes
- Repère le nombre n de valeurs à trier.
- Estime le nombre de niveaux de divisions équilibrées : environ log₂(n).
- Compte le travail total des fusions sur un niveau : proportionnel à n.
- Multiplie les ordres de grandeur pour obtenir O(n log n) dans le pire cas.
Exemples
- Pour n = 8, le logarithme en base 2 de 8 vaut 3 : il y a donc 3 niveaux, chacun traitant au total 8 valeurs, soit un travail de l’ordre de 8 × 3.
- Pour une liste de 16 valeurs, les divisions équilibrées mènent à environ 4 niveaux de fusion, avec un travail total de l’ordre de 16 par niveau.
Pièges fréquents
- Annoncer O(log n) parce qu’il n’y a que log₂(n) niveaux : les n valeurs sont aussi traitées à chaque niveau.
- Présenter O(n log n) comme un nombre exact d’opérations ou des secondes : cette notation décrit une croissance asymptotique, sans constante ni durée machine.
