Exactement combien de comparaisons ne de fusion tri faire?

Nous allons voir si nous pouvons faire ce travail!

Dans la fusion de tri, à chaque niveau de la récursivité, nous ne les suivants:

1. Diviser le tableau en deux.
2. Trier récursivement chaque moitié.
3. Utiliser l'algorithme de fusion de combiner les deux moitiés ensemble.

Alors, comment de nombreuses comparaisons sont effectuées à chaque étape? Ainsi, la fracture étape ne pas faire de comparaisons; simplement, il divise le tableau en deux. L'étape 2 n'est pas (directement) rend la comparaison; toutes les comparaisons sont faites par des appels récursifs. Dans l'étape 3, nous avons deux matrices de taille n/2 et le besoin de les fusionner. Cela nécessite tout au plus n comparaisons, puisque chaque étape de l'algorithme de fusion fait une comparaison, puis consomme une partie de l'élément de tableau, donc on ne peut pas faire plus que n comparaisons.

La combinaison de cet ensemble, on obtient l'récurrence:

C(1) = 0
C(n) = 2C(n /2) + n

(Comme mentionné dans les commentaires, le terme linéaire est plus précisément (n - 1), bien que cela ne change pas la conclusion générale. Nous allons utiliser au-dessus de la récidive, comme une limite supérieure.)

Pour simplifier, nous allons définir n = 2^k et la réécriture de cette récurrence en termes de k:

C'(0) = 0
C'(k) = 2C'(k - 1) + 2^k

Les premiers termes sont ici 0, 2, 8, 24, ... . Cela ressemble à quelque chose comme k 2^k, et nous pouvons le prouver par induction. Notre scénario de base, lorsque k = 0, le premier terme est 0, et la valeur de k 2^k est également 0. Pour l'étape inductive, supposons que la revendication est pour certains k et envisager k + 1. Ensuite, la valeur est de 2(k 2^k) + 2^{k + 1} = k 2 ^{k + 1} + 2^{k + 1} = (k + 1)2^{k + 1}, de sorte que la revendication est pour k + 1, de l'achèvement de l'induction. Ainsi, la valeur de C'(k) est k 2^k. Puisque n = 2 ^k, cela signifie que, en supposant que n est une puissance parfaite de deux, avons-nous que le nombre de comparaisons est

C(n) = n lg n

Impressionnant, c'est mieux que quicksort! Alors pourquoi sur la terre est quicksort plus rapide que la fusion de tri? Cela a à voir avec d'autres facteurs qui n'ont rien à voir avec le nombre de comparaisons. Principalement, depuis quicksort fonctionne à la place tandis que la fusion tri fonctionne hors de l'endroit, la localité de référence n'est pas aussi bonne dans la fusion de sorte que c'est dans quicksort. C'est un facteur énorme que quicksort est beaucoup, beaucoup mieux que la fusion de tri dans la pratique, étant donné que le coût d'un cache miss est assez énorme. En outre, le temps nécessaire pour trier un tableau n'est pas seulement le nombre de comparaisons en compte. D'autres facteurs, comme le nombre de fois que chaque élément du tableau est déplacé peut également être important. Par exemple, dans la fusion de tri nous avons besoin d'allouer de l'espace pour la mémoire tampon éléments, déplacer les éléments de sorte qu'ils peuvent être fusionnées, puis de fusionner de nouveau dans le tableau. Ces mouvements ne sont pas prises en compte dans notre analyse, mais ils ont certainement ajouter. Comparez cela à quicksort de l'étape de partitionnement, qui se déplace à chaque élément du tableau exactement une fois et reste à l'intérieur du tableau original. Ces facteurs supplémentaires, pas le nombre de comparaisons, de dominer l'algorithme du moteur d'exécution.

Cette analyse est un peu moins précis que le choix optimal, mais Wikipédia confirme que l'analyse est à peu près n lg n et que c'est en effet de moins en moins de comparaisons que quicksort la moyenne des cas.

Espérons que cette aide!

La fusion de deux tableaux triés (ou des listes), de la taille k resp. m prend k+m-1 comparaisons au plus, min{k,m} au mieux. (Après chaque comparaison, nous pouvons écrire une valeur de la cible, lorsque l'un des deux est épuisé, pas plus que les comparaisons sont nécessaires.)

Laisser C(n) être le pire des cas certain nombre de comparaisons pour un mergesort d'un tableau (une liste) de n éléments.

Puis nous avons C(1) = 0, C(2) = 1, assez évidemment. De plus, nous avons la récurrence

C(n) = C(floor(n/2)) + C(ceiling(n/2)) + (n-1)

Une simple induction montre

C(n) <= n*log_2 n

D'autre part, il est facile de voir que nous pouvons arbitrairement proche de la limite (pour chaque ε > 0, on peut construire des cas, avoir besoin de plus de (1-ε)*n*log_2 n comparaisons), de sorte que la constante de mergesort est 1.