rekursive mergesort Funktionsanalyse

Question

brauche Hilfe bei Fragen von Data Structure Kurs: ich diese rekursive Funktion von mergesort gegeben wurde (Pseudocode):

Mergesort_1/3(A, p, r) 
if p < r 
    then q = (p+(r-p)/3) // round the result down 
     Mergesort_1/3 (A,p,q)    
       Mergesort_1/3 (A,q+1,r) 
       Merge(A,p,q,r) 

und das sind die Fragen:

1. Sei T (n) die Worst-Case-Laufzeit von Mergesort _1/3. Schreibe die rekursive Funktion für T (n). Gib eine kurze Erklärung.
2. Beweisen Sie, dass T (n) = Ω (n log n)

Answer 1

Der Kern des klassischen mergesort ist die folgende Rekursion:

• Split eine ungeordnete Liste in zwei Hälften. Es genügt, die Limit-Offsets der Teillisten zu berechnen.
• Wenden Sie den Mergesort auf jede der Teillisten an.
  Nach diesem Schritt werden die Teillisten sortiert.
• Fügen Sie die sortierten Teillisten zusammen, indem Sie die Elemente beider Listen in ihrer jeweiligen Reihenfolge untersuchen, indem Sie in der Liste mit dem kleineren Element abgleichen und fortfahren.

Lassen Sie TC(n) die Zeit Komplexität des klassischen Mergesort sein. Die zuvor erwähnten Schritte nehmen O(1) (*), 2*O(TC(ceil(n/2))) bzw. O(n). Dies führt zu der Rekursion TC(n) = cc_0 + cc_1 * n + 2 * TC(ceil(n/2)).

Betrachten Sie den verallgemeinerten Mergesort, bei dem Listen ungleichmäßig aufgeteilt sind, jedoch immer mit demselben Verhältnis. Die Komplexität der Aufspaltung und Zusammenführung bleibt die gleiche, an die Rekursion verleihen TG(n) = ca_0 + ca_1 * n + TG(1/a * n + 1) + TG((a-1)/a * n + 1)) für die generali mergesort (unter Verwendung von TG(x+1) anstelle von TG(ceil(x)); ca_0, ca_1 wobei die Konstanten in der Notation O(_) hidden; a=3 für mergesort_1/3).

Diese Wiederholung kann mit der Akra-Bazzi-Method gelöst werden. Zu diesem Zweck muss die Wiederholung

TG(x) = g(x) + \sum_i=1..k (a_i * TG(b_i * x + h_i(x)) ; x >= x_0. 

mit

a_i, b_i const. 
a_i > 0 
0 < b_i < 1 
|g(x)| = O(x^c); c const. 
|h(x)| = O(x/(log(x))^2) 

als

geschrieben werden, die durch das Setzen getan werden kann ...

k  = 2 
a_1 = 1 
a_2 = 1 
b_1 = 1/a 
b_2 = (a-1)/a 
g(x) = ca_0 + ca_1 * x 
h_1(x) = 1 
h_2(x) = 1 
x_0 = 2 

-> TG(x) = ca_0 + ca_1 * n + 1 * TG(1/a * x + 1) + 1 * TG((a-1)/a * x + 1) ; x >= x_0. 

Das Akra-Bazzi-Theorem erfordert der Exponent ist in \sum_i=1..k (a_i * (b_i)^p) = 1 zu finden. Dann gilt:

TG(x) = Θ (x^p \integral_(1, x) (g(u)/(u^(p+1)) du)) 

Insbesondere

a_1 * b_1^p + a_2 * b_2^p = 1 
=> (1/a)^p + ((a-1)/a)^p  = 1 
<=> p = 1 

... und so ...

TG(x) = Θ (x \integral_(1, x) ((ca_0 + ca_1 * u)/u^2 du)) 
     = Θ (x [ - ca_0/u + ca_1 * log(u) ]_(1,x)) 
     = Θ (- ca_0 + ca_1 * x * log(x) + ca_0 * x - ca_1 * x * log(1)) 
     = Θ (x * log(x)) 

(*) Genau genommen dies nicht korrekt ist, da Grundrechenarten auf binäre Darstellungen und Speicherzugriff O(log n) sind. Dies macht jedoch asymptotisch für Θ(n log n) Komplexität keinen Unterschied.

Answer 2

Statt zwei erstellt dieser Mergesort Partitionen die Daten in drei gleich großen Teilen. Sie reduzieren also ein Problem der Größe n auf drei Probleme der Größe n/3. Außerdem müssen Sie beim Zusammenführen alle drei n/3 sortierten Stücke durchlaufen, was dazu führt, dass Sie insgesamt n Elemente durchlaufen. Somit kann die Wiederholung geschrieben werden als:

• T (n) = 3 T (n/3) + O (n)

Using Master Theorem: Hier a = 3, b = 3 und c = 1. Protokoll _b a = Protokoll 3 = 1 = c.

So wird die Wiederholung fallen im zweiten Fall und T (n) = Θ (n ^c * Log (n)) = Θ (n * Log (n)).