Beweisen Sie, dass die Laufzeit des optimierten Mergesorts Theta(NK + Nlog(N/K)) ist.

Question

Okay, ich weiß, dass Mergesort eine Worst-Case-Zeit von Theta (NlogN) hat, aber sein Overhead ist hoch und manifestiert sich am unteren Ende des Rekursionsbaums, wo die Zusammenführungen vorgenommen werden.Jemand hat vorgeschlagen, dass wir die Rekursion stoppen, sobald die Größe K erreicht, und an diesem Punkt zur Einfügungssortierung wechseln.Ich muss beweisen, dass die Laufzeit dieser modifizierten Wiederholungsbeziehung Theta(NK + Nlog(N/k)) beträgt.Ich weiß nicht, wie ich dieses Problem angehen soll.

Answer 1

Vielleicht ist es ein guter Anfang, sich die Wiederholungsbeziehung für dieses Problem anzusehen.Ich stelle mir vor, dass es für einen typischen Mergesort etwa so aussehen würde:

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

d.h.Sie teilen das Problem in zwei halb so große Teilprobleme auf und führen dann N Arbeiten aus (die Zusammenführung).Wir haben einen Basisfall, der konstante Zeit benötigt.

Wenn wir dies als Baum modellieren, haben wir:

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)

Dies ergibt eine Erweiterung von

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

Wir müssen also wirklich nur sehen, wie tief es geht.Wir wissen, dass die iDie Ebene bearbeitet Teilprobleme N / 2^i in Größe.Also unsere Blattknoten (T(1)) treten auf Ebene auf L Wo N / 2^L = 1:

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

Unsere Laufzeit ist also N log N.

Jetzt führen wir die Einfügungssortierung ein.Unser Baum wird ungefähr so ​​aussehen

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

Mit anderen Worten: Wir werden es irgendwann tun L lösen müssen N/K Probleme beim Einfügen und Sortieren der Größe K.Die Einfügesortierung hat im ungünstigsten Fall eine Laufzeit von K^2.Bei den Blättern haben wir also so viel Arbeit in Summe:

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

Aber wir müssen auch eine Menge Zusammenführungen durchführen, die Kosten verursachen N pro Ebene des Baums, wie zuvor erläutert.Kehren wir zu unserer vorherigen Methode zurück und suchen wir nach L (Die Anzahl der Ebenen, bevor wir Teilprobleme der Größe erreichen K und damit zum Einfügen wechseln):

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

Insgesamt haben wir also

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

Es ist zu lange her, dass ich Algorithmen verwendet habe, um Ihnen eine Beweisskizze zu liefern, aber das sollte Ihre Neuronen zum Leuchten bringen.