Livre_silo 30 août 2013 16:32 Page 326
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
326
Informatique pour tous
SAVOIR-FAIRE Distinguer par leurs complexités deux algorithmes
résolvant un même problème
Il convient tout d’abord de s’assurer que les algorithmes résolvent bien le même problème : il n’ est pas rare que leurs conditions d’utilisation soient différentes, ce qui rend
moins pertinente une comparaison de complexité.
• On s’intéressera d’abord à la complexité en temps dans le pire des cas, qui est
souvent la plus représentative.
• On discutera cependant si ce pire cas a des chances de se présenter dans des situations réelles.
• On n’ oubliera pas d’étudier la complexité en espace, qui peut départager des algorithmes de performances par ailleurs similaires.
Exercice 13.6 Quelles sont les différences entre les algorithmes de tri rapide et de tri fusion du point de
vue de la complexité en temps et en espace ?
Quelles conséquences cela a-t-il pour leur utilisation ?
On rappelle tout d’abord que ces deux tris fonctionnent sur les mêmes entrées sans conditions particulières.
• Le tri rapide a une complexité en temps quadratique dans le pire cas. Si on veut être certain que ce cas
ne se présente pas, on choisira plutôt le tri fusion, qui est au pire en O(n log n).
• Ces deux tris ont une complexité moyenne en O(n log n), ce qui signifie qu’en général ils auront des
performances comparables, en particulier si la répartition des données dans le tableau à trier n’est pas
trop particulière.
• Le tri fusion a une complexité en espace légèrement supérieure à celle du tri rapide puisque la fusion ne
s’opère pas en place. Dans un cas où la mémoire est une ressource critique, on évitera donc de choisir
le tri fusion.
POUR ALLER PLUS LOIN La complexité optimale du tri
La meilleure complexité que l’on peut espérer d’un tri effectuant uniquement des comparaisons d’éléments est en O(N log N ). En effet, on peut visualiser un tel algorithme comme
un arbre binaire. Chaque nœud interne représente une comparaison effectuée, le sousarbre gauche (resp. droit) représentant la suite de l’algorithme lorsque le test est positif
(resp. négatif). Chaque feuille représente un résultat possible, c’est-à-dire une permutation
effectuée sur la séquence initiale. Si on suppose les N éléments distincts, il y a N ! permutations possibles, donc au moins N ! feuilles à cet arbre. Sa hauteur est donc au moins égale
à log N !. Or le plus long chemin de la racine à une feuille représente le plus grand nombre
de comparaisons effectuées par l’algorithme sur une entrée. Il existe donc une entrée pour
laquelle le nombre de comparaisons est au moins log N !. Par la formule de Stirling, on sait
que log N ! ∼ N log N . Pour une démonstration plus détaillée, on pourra consulter The Art
of Computer Programming [Vol 3, Sec. 5.3].
Exercice 13.7 Dérouler à la main l’algorithme de tri fusion sur le tableau [5,40,2,18,17,3,0,1,14].
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
326
Informatique pour tous
SAVOIR-FAIRE Distinguer par leurs complexités deux algorithmes
résolvant un même problème
Il convient tout d’abord de s’assurer que les algorithmes résolvent bien le même problème : il n’ est pas rare que leurs conditions d’utilisation soient différentes, ce qui rend
moins pertinente une comparaison de complexité.
• On s’intéressera d’abord à la complexité en temps dans le pire des cas, qui est
souvent la plus représentative.
• On discutera cependant si ce pire cas a des chances de se présenter dans des situations réelles.
• On n’ oubliera pas d’étudier la complexité en espace, qui peut départager des algorithmes de performances par ailleurs similaires.
Exercice 13.6 Quelles sont les différences entre les algorithmes de tri rapide et de tri fusion du point de
vue de la complexité en temps et en espace ?
Quelles conséquences cela a-t-il pour leur utilisation ?
On rappelle tout d’abord que ces deux tris fonctionnent sur les mêmes entrées sans conditions particulières.
• Le tri rapide a une complexité en temps quadratique dans le pire cas. Si on veut être certain que ce cas
ne se présente pas, on choisira plutôt le tri fusion, qui est au pire en O(n log n).
• Ces deux tris ont une complexité moyenne en O(n log n), ce qui signifie qu’en général ils auront des
performances comparables, en particulier si la répartition des données dans le tableau à trier n’est pas
trop particulière.
• Le tri fusion a une complexité en espace légèrement supérieure à celle du tri rapide puisque la fusion ne
s’opère pas en place. Dans un cas où la mémoire est une ressource critique, on évitera donc de choisir
le tri fusion.
POUR ALLER PLUS LOIN La complexité optimale du tri
La meilleure complexité que l’on peut espérer d’un tri effectuant uniquement des comparaisons d’éléments est en O(N log N ). En effet, on peut visualiser un tel algorithme comme
un arbre binaire. Chaque nœud interne représente une comparaison effectuée, le sousarbre gauche (resp. droit) représentant la suite de l’algorithme lorsque le test est positif
(resp. négatif). Chaque feuille représente un résultat possible, c’est-à-dire une permutation
effectuée sur la séquence initiale. Si on suppose les N éléments distincts, il y a N ! permutations possibles, donc au moins N ! feuilles à cet arbre. Sa hauteur est donc au moins égale
à log N !. Or le plus long chemin de la racine à une feuille représente le plus grand nombre
de comparaisons effectuées par l’algorithme sur une entrée. Il existe donc une entrée pour
laquelle le nombre de comparaisons est au moins log N !. Par la formule de Stirling, on sait
que log N ! ∼ N log N . Pour une démonstration plus détaillée, on pourra consulter The Art
of Computer Programming [Vol 3, Sec. 5.3].
Exercice 13.7 Dérouler à la main l’algorithme de tri fusion sur le tableau [5,40,2,18,17,3,0,1,14].