Lösen der rekursiven Gleichung $T(n)=T(k)+T(n-k-1)+O(n)$
Die Frage ist im Titel klar. Ich versuche, diese Rekursion zu lösen, um zu zeigen, dass der schlimmste Fall eines Quicksort-Algorithmus auftritt, wenn$k=0$, kann es aber nicht. Ich könnte die folgenden speziellen Fälle ausführen (indem ich wiederholt dieselbe Rekursion verwende):
1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$
Kann mir bitte jemand helfen, diesen allgemeinen Fall zu lösen (oder zumindest einen anderen Weg vorschlagen, um zu beweisen, dass der schlimmste Fall der Fall ist? $k=0$)?
PS Ich kenne den Satz des Meisters nicht, daher würde ich mich über eine Lösung ohne diese freuen (falls dies hier anwendbar ist).
Antworten
Betrachten Sie die Wiederholung $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$Dies ist eine Formalisierung der Worst-Case-Laufzeit von Quicksort. Zeigen wir durch Induktion, dass das Maximum bei erreicht wird$k = 0$ (oder $k = n$). Wir werden dies zeigen und gleichzeitig das zeigen$T(n) = \frac{n(n+1)}{2}$.
Der Basisfall, $n=0$, ist klar. Nehmen wir das an$T(m) = \frac{m(m+1)}{2}$ für alle $m \leq n$und überlegen $T(n+1)$. Die Funktion$T(k)$ ist im Intervall konvex $[0,n]$ (Wir erweitern es auf reale Werte mit der gleichen Formel), und so das Maximum von $T(k) + T(n-k)$ erreicht wird bei $k=0$ (oder $k=n$). Deshalb$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$
Anstatt mit Konvexität zu argumentieren, können wir auch direkt argumentieren: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ was eindeutig (eindeutig) maximiert ist, wenn $k = 0$ oder $k = n$.