Prouver durée est de mergesort optimisé est thêta (NK + Nlog (N / K))?
-
27-10-2019 - |
Question
D'accord, je sais que Mergesort a un pire moment de cas de thêta (NlogN), mais ses frais généraux est élevé et se manifeste près du fond de l'arbre de récursivité où les fusions sont faites. Quelqu'un a proposé que nous nous arrêtons la récursion fois la taille atteint K et passer à d'insertion sorte à ce moment-là. Je dois prouver que le temps d'exécution de cette relation de récurrence est modifiée thêta (NK + Nlog (N / k))? Je suis à BLANKING la façon d'aborder ce problème ..
La solution
Peut-être un bon point de départ est d'examiner la relation de récurrence de ce problème. J'imagine pour mergesort typique, il ressemblerait à quelque chose comme ceci:
T(N) = 2 * T(N / 2) + N
i.e.. vous divisez le problème en 2 de sous-problèmes moitié de la taille, puis effectuer un travail N (la fusion). Nous avons un cas de base qui prend du temps constant.
Modélisation cela comme un arbre, nous avons:
T(N) = N -> T(N / 2)
-> T(N / 2)
= N -> (N / 2) -> T(N / 4)
-> T(N / 4)
-> (N / 2) -> T(N / 4)
-> T(N / 4)
Cela donne une expansion de
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
Alors, vraiment nous avons juste besoin de voir comment il va en profondeur. Nous savons que le niveau i
th fonctionne sur N / 2^i
taille sous-problèmes. Ainsi, nos nœuds feuilles (de T(1)
) se produisent au niveau L
où N / 2^L = 1
:
N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L
Donc, notre moteur d'exécution est N log N
.
Maintenant, nous introduisons sorte d'insertion. Notre arbre ressemblera à quelque chose comme ceci
T(N) = ... -> I(K)
-> I(K)
...x N/K
En d'autres termes, nous allons à un certain niveau L
doivent résoudre des problèmes de tri d'insertion de N/K
de taille K
. L'insertion a une sorte d'exécution pire cas de K^2
. Donc, les feuilles, nous avons beaucoup de travail ce au total :
(N / K) * I(K)
= (N / K) * K * K
= N * K
Mais nous avons aussi un groupe de fusion pour faire aussi bien, à un coût de N
par niveau de l'arbre comme expliqué précédemment. Pour en revenir à notre méthode précédente, Trouvons L
(le nombre de niveaux avant d'atteindre la taille K
sous-problèmes et passer ainsi à l'insertion):
N / 2^L = K
N / K = 2^L
L = log (N/K)
Au total, nous avons
O(N) = N * K + N * log (N/K)
Il a été trop longtemps que je pris des algorithmes pour vous donner une esquisse de preuve, mais qui devrait obtenir vos neurones de tir.