Wie man eine Wiederholungsgleichung für die Laufzeit eines Teile-und-Herrsche-Algorithmus angibt

Also,$T(n) = T(a) + T(b) + 2n$im ersten Fall mit$a,b$begrenzt, wie Sie erwähnt haben

Lassen Sie uns zuerst das Problem in Bezug auf eine explizite Wiederholungsrelation formulieren.

Lassen$a _ 1 = a _ 2 = 1$Und$b _ 1 = b _ 2 = \frac 1 2$, und betrachten Sie die Funktionen$T , h _ 1 , h _ 2 , g$und mit der Eigenschaft, dass

$$T ( x ) = g ( x ) + a _ 1 T \big( b _ 1 x + h _ 1 ( x ) \big) + a _ 2 T \big( b _ 2 x + h _ 2 ( x ) \big) \text .$$ Vermute das auch$| h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x 4$. Finden Sie asymptotische Schranken für$T$, Wenn$g ( x ) = 2 x$, und wann$g ( x ) = x ^ 2$.

Ich habe das Problem absichtlich wie oben formuliert, so dass es der Form ähnelt, die im Akra-Bazzi-Theorem erscheint , das eine der bekanntesten Verallgemeinerungen des Master-Theorems ist . Wie Sie in Leightons Notiz zum Akra-Bazzi-Theorem sehen können , funktioniert die gegebene asymptotische Grenze des Theorems nur dann garantiert, wenn es eine positive Konstante gibt$\epsilon$so dass wir haben$| h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x { ( \log x ) ^ { 1 + \epsilon } }$für alle groß genug$x$(zusammen mit anderen Anforderungen, die in unserem Problem gelten). Leider ist dies bei unserem Problem nicht der Fall, und Sie können den Hauptsatz oder seine bekannten Verallgemeinerungen nicht wie erwartet verwenden. Aber glücklicherweise funktioniert die durch den Satz gegebene Wachstumsreihenfolge in unserem Problem aus einem anderen einfachen Grund. Wir haben also mit dem verallgemeinerten Hauptsatz eine gute Vermutung und müssen nur selbst einen Beweis liefern. Als$p = 1$ist die eindeutige reelle Zahl befriedigend$a _ 1 b _ 1 ^ p + a _ 2 b _ 2 ^ p = 1$(die kritische Kraft), die vorgegebene Wachstumsreihenfolge$\Theta \bigg( x ^ p \left( 1 + \int _ 1 ^ x \frac { g ( u ) } { u ^ { p + 1 } } \ \mathrm d u \right) \bigg)$wird$\Theta ( x \log x )$falls$g ( x ) = 2 x$, Und$\Theta \left( x ^ 2 \right)$falls$g ( x ) = x ^ 2$.

Um zu sehen, warum die Grenzen funktionieren, beachten Sie, dass beide$x \mapsto x \log x$Und$x \mapsto x ^ 2$sind differenzierbare konvexe Funktionen (in unserem Interessenbereich, sagen wir$x \ge 1$). So ihre Derivate,$x \mapsto 1 + \log x$Und$x \mapsto 2 x$, sind streng steigend und daher injektiv. Betrachten Sie eine differenzierbare reellwertige Funktion$f$in einem Intervall definiert$I = \left[ \frac n 2 - m , \frac n 2 + m \right]$für etwas positives$n$Und$m$, so dass seine Ableitung$f '$ist streng steigend. Definieren$F : I \to \mathbb R$mit$F ( a ) = f ( a ) + f ( n - a )$. Dann$F$ist differenzierbar und$F ' ( a ) = f ' ( a ) - f ' ( n - a )$. Als$f '$ist injektiv, der Wert von$F '$kann nur dann Null werden$a = n - a$, dh$a = \frac n 2$. Als Extrema von$F$kann nur an den Endpunkten von passieren$I$oder wo der Wert von$F '$Null wird, können wir das für alle überprüfen$a \in I$,

Fall$T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + 2 n$

Wähle positive Konstanten$c _ 1 \le 2$Und$c _ 2 \ge \frac 1 { 1 - \frac 3 8 \log _ 2 3 }$so dass wir haben

Fall$T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + n ^ 2$

Wähle positive Konstanten$c _ 1 \le 2$Und$c _ 2 \ge \frac 8 3$so dass wir haben