Wykazać, że czas działania zoptymalizowanego mergesort to theta (NK + Nlog (N/K))?

Question

Dobra, wiem, że Mergesort ma najgorszy przypadek czasu theta (NlogN), ale jego obciążenie jest wysokie i pojawia się w dolnej części drzewa rekursji, gdzie dokonuje się scaleń. Ktoś zaproponował, abyśmy zatrzymali rekursję, gdy rozmiar osiągnie K i przełączy się na sortowanie w tym miejscu. Muszę udowodnić, że czas działania tej zmodyfikowanej relacji jest to theta (NK + Nlog (N/k))? Nie pamiętam, jak podejść do tego problemu ..

Answer 1

Być może dobrym początkiem jest przyjrzeć się relacji nawyków dla tego problemu. Wyobrażam sobie, dla typowego mergesort to wyglądać mniej więcej tak:

T(N) = 2 * T(N/2) + N 

tj jesteś podzielenie problemu na 2 podproblemów o połowę mniejszy, a następnie wykonywania pracy N (scalanie). Mamy przypadek bazowy, który zajmuje stały czas.

Modelowanie to jako drzewo mamy:

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) 

Daje ekspansję

T(N) = N + 2N/2 + 4N/4 + ... 
    = N + N + N ... 

Tak naprawdę po prostu trzeba zobaczyć, jak głęboko to idzie. Wiemy, że poziom i th działa na subproblemach o rozmiarze N/2^i. Więc nasze węzły liściowe (T(1)) występują na poziomie L gdzie N/2^L = 1:

N/2^L = 1 
N = 2^L 
log N = log(2^L) 
log N = L 

więc nasz czas pracy jest N log N.

Teraz wprowadzamy sortowanie. Nasze drzewo będzie wyglądać następująco

T(N) = ... -> I(K) 
      -> I(K) 
      ...x N/K 

Innymi słowy, będziemy na pewnym poziomie L musiał rozwiązać N/K problemy Sortowanie przez wstawianie o rozmiarze K. Sortowanie wstawiania ma najgorszy przypadek wykonania: K^2. Tak na liście mamy to dużo pracy całkowitego:

(N/K) * I(K) 
= (N/K) * K * K 
= N * K 

Ale mamy też kilka łączących zrobić, jak również, kosztem N na poziomie drzewa jak wyjaśniono wcześniej. Wracając do naszej poprzedniej metodzie, znajdźmy L (liczbę poziomów, zanim dotrzemy podproblemów o rozmiarze K i tym samym przejść do wstawienia):

N/2^L = K 
N/K = 2^L 
L = log (N/K) 

Więc w sumie mamy

O(N) = N * K + N * log (N/K) 

Minęły zbyt długo, odkąd wziąłem algorytmy, by dać ci szkic dowodowy, ale to powinno spowodować, że twoje neurony wystrzelą.