Nombre de Comparaisons dans la Fusion-Tri

Pourquoi compter les comparaisons

Il y a fondamentalement deux opérations de tout algorithme de tri: comparaison de données et de déplacement des données. Dans de nombreux cas, la comparaison sera plus cher que le déplacement. Pensez à longues chaînes dans une référence à base de système de typage: le déplacement de données sera tout simplement l'échange de pointeurs, mais la comparaison peut nécessiter une itération sur une grande partie de l'cordes avant de la première différence est constatée. Ainsi, dans ce sens, la comparaison est peut-être l'opération de se concentrer sur.

Pourquoi un compte exact de

Les chiffres semblent être plus détaillée: au lieu de simplement donner quelques Landau symbole (grand-Oh notation) pour la complexité, vous obtenez un nombre réel. Une fois que vous avez décidé ce qu'est une opération de base est, comme une comparaison dans ce cas, cette approche qui fait le comptage des opérations devient possible. Ceci est particulièrement important lorsque l'on compare les constantes cachées par le Landau symbole, ou lors de l'examen de la non-asymptotique cas de petites entrées.

Pourquoi ce compte exact de la formule de

Noter que tout au long de cette discussion, lg désigne le logarithme de base 2. Lorsque vous fusionnez-tri n, vous avez ⌈lg n⌉ niveaux de fusions. Supposons que vous placez ⌈lg n⌉ pièces de monnaie sur chaque élément pour être triés, et une fusion des coûts d'une pièce de monnaie. Ce sera certainement assez pour payer toutes les fusions, comme chaque élément sera inclus dans ⌈lg n⌉ fusionne, et chaque fusion, ne prendra pas plus de comparaisons que le nombre d'éléments impliqués. Donc, c'est le n⌈lg n⌉ de votre formule.

Comme une fusion de deux tableaux de longueur m et n ne prend que m + n − 1 comparaisons, vous avez encore des pièces à gauche à la fin, un de chaque fusion. Laissez-nous, pour le moment, supposons que toutes notre gamme de longueurs sont des puissances de deux, c'est à dire que vous avez toujours m, = n. Alors le nombre total de fusions est n − 1 (somme des puissances de deux). En utilisant le fait que n est une puissance de deux, cela peut aussi être écrit comme 2^{⌈lg n⌉} − 1, et en soustrayant ce nombre de retours de pièces de monnaie à partir du nombre de toutes les pièces rendements n⌈lg n⌉ − 2^{⌈lg n⌉} + 1 tel que requis.

Si n est 1 de moins que d'une puissance de deux, puis il y a ⌈lg n⌉ fusionne où un élément est impliqué. Cela comprend une fusion de deux un élément des listes qui permet de prendre une pièce de monnaie et qui, maintenant, disparaît complètement. De sorte que le coût total réduit par ⌈lg n⌉, ce qui est exactement le nombre de pièces que vous auriez placé sur le dernier élément si n ont une puissance de deux. Donc, vous avez à la place de moins en moins de pièces de monnaie à l'avant, mais que vous obtenez en retour le même nombre de pièces. C'est la raison pour laquelle la formule a 2^{⌈lg n⌉} au lieu de n: la valeur reste la même si vous goutte à une plus petite puissance de deux. Le même argument, si la différence entre n et la puissance de deux est plus grand que 1.

Dans l'ensemble, il en résulte la formule donnée dans le Wikipédia:

n ⌈lg n⌉ − 2^{⌈lg n⌉} + 1

Note: je suis assez heureux avec le dessus de la preuve. Pour ceux qui aiment ma formulation, n'hésitez pas à les distribuer, mais n'oubliez pas de les attribuer à moi comme le licence exige.

Pourquoi cette limite inférieure

De prouver la limite inférieure de la formule, nous allons écrire ⌈lg n⌉ = lg n + d avec 0 ≤ d < 1. Maintenant la formule ci-dessus peut être écrite comme

n (lg n + d) − 2^{lg n + d} + 1 =
n lg n + nd − n2^d + 1 =
n lg n − n(2^d − d) + 1 ≥
n lg n − n + 1

où l'inégalité est vraie parce que 2^d − d ≤ 1 pour 0 ≤ d < 1

Pourquoi cette limite supérieure

Je dois l'avouer, je suis un peu perplexe, pourquoi quelqu'un aurait le nom de n lg n + n + O(lg n) comme une limite supérieure. Même si vous avez voulu éviter que le plancher de la fonction, le calcul ci-dessus suggère quelque chose comme n lg n − 0.9n + 1 en tant que bien plus serré qu'à la limite supérieure pour la formule exacte. 2^d − d a son minimum (ln(ln(2)) + 1)/ln(2) ≈ 0.914 pour d, = −ln (- ln(2))/ln(2) ≈ 0.529.

Je ne peux que deviner que le prix de la formule apparaît dans certains de publication, soit comme plutôt lâche lié pour cet algorithme, ou que le nombre exact de comparaisons pour une autre algorithme qui est comparée avec celle-ci.

---

(Deux comptes différents)

Ce problème a été résolu par le commentaire ci-dessous, une formule a été cité de façon incorrecte.

est égal à (n lg n - n + 1); en fait, c'est entre (n lg n - n + 1) et (n lg n + n + O(lg n))

Si la première partie est vraie, la seconde est trivialement vrai, mais explicitement indiquant la limite supérieure est inutile. Je n'ai pas regardé les détails moi-même, mais ces deux énoncés semblent étranges lorsqu'ils sont pris ensemble comme ça. Le premier est vraiment vrai, dans ce cas, je serait omettre le second, en tant que seule source de confusion, ou la deuxième est vrai, dans ce cas, le premier est mauvais et doit être omise.

OriginalL'auteur MvG