Prouver durée est de mergesort optimisé est thêta (NK + Nlog (N / K))?

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 ..

Answer 1

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 ith 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.