Strenger Beweis für die Gültigkeit der Annahme

Der Hauptsatz ist ein schönes Werkzeug zum Lösen bestimmter Arten von Wiederholungen . Wir beschönigen jedoch häufig einen integralen Bestandteil, wenn wir ihn auftragen. Beispielsweise gehen wir bei der Analyse von Mergesort gerne ab

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

unter Berücksichtigung von nur . Wir versichern uns, dass dieser Schritt gültig ist - das heißt, - weil sich "gut" verhält. Im Allgemeinen nehmen wir für den gemeinsamen Nenner an . $n=2^k$ $T \in \Theta(T')$ $T$ $n=b^k$ $b$

Es ist einfach, Wiederholungen zu konstruieren, die diese Vereinfachung nicht zulassen, indem bösartiges . Zum Beispiel oben Wiederholung für / mit $f$ $T\,$ $\,T'$

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

ergibt unter Verwendung des Hauptsatzes auf die übliche Weise, aber es gibt eindeutig eine Subsequenz, die wie wächst . Sehen Sie sich hier ein weiteres Beispiel an. $\Theta(n)$ $\Theta(n \log n)$

Wie können wir das "schön" rigoros machen? Ich bin mir ziemlich sicher, dass Monotonie ausreicht, aber nicht einmal die einfache Mergesort-Wiederholung ist monoton; es gibt eine periodische Komponente (die asymptotisch dominiert wird). Reicht es aus, zu untersuchen , und welche notwendigen und ausreichenden Bedingungen für sicher, dass der Hauptsatz funktioniert? $f$ $f$

asymptotics proof-techniques recurrence-relation master-theorem Raphael
quelle

Eine weitere Annahme zu denselben Ergebnissen ist der Akra-Bazzi-Satz "Über die Lösung linearer Rekursionsgleichungen", Computational Optimization and Applications, 10 (2), 195-210 (1998), oder Drmota und Szpankowski "A Master Theorem for Discrete Divide and Conquer Recurrences ", SODA'11 < dl.acm.org/citation.cfm?id=2133036.2133064 >.

Vonbrand

Hier ist ein Link zum obigen Artikel, der sich nicht hinter einer Paywall befindet.

Paresh

IIRC dies wird in CLRS Kapitel 4 besprochen.

Kaveh

@Kaveh Danke für den Hinweis. Zum größten Teil nennen sie es "erträgliche Schlamperei"; Dies ist in ihrem Zusammenhang in Ordnung, da sie davon ausgehen, dass Sie nur eine Hypothese ableiten, die später durch Induktion als richtig erwiesen wird. Sie erwähnen die Gefahren (4.6). In 4.6.2 geben sie einen Beweis, aber es ist auf hohem Niveau und sie sagen nicht explizit, welche Einschränkungen für

müssen. Es scheint also so etwas wie "

so, dass die Mathematik durchgeht" zu sein, was meiner Meinung nach hauptsächlich erfordert, dass

eine "nette"

Klasse hat.

T

$T$

T

$T$

f

$f$

Θ

$\Theta$

Raphael

Wenn Sie keine ähnlichen Größen haben, können Sie im Allgemeinen die Akra-Bazzi-Methode verwenden, die eine Verallgemeinerung des Hauptsatzes ist. Um eine bestimmte Funktion in etwas zu ändern, das in diesem Satz funktioniert, ist ein kleiner Trick erforderlich. Dies wird normalerweise verwendet, um die Komplexität der Zeit zu beweisen.

In dieser Antwort gehen wir davon aus, dass und nicht negativ sind. Unser Beweis funktioniert immer dann, wenn für ein monotones . Dies schließt Ihr Mergesort-Beispiel mit ein, in dem und jede Funktion mit polynomieller Wachstumsrate (oder sogar ). $f$ $T$ $f = \Theta(g)$ $g$ $f=\Theta(n)$ $\Theta(n^a \log^b n)$

Betrachten wir zunächst den Fall, dass nicht abnehmend ist (wir werden diese Annahme später lockern). Wir konzentrieren uns auf Ihre Diese Wiederholung benötigt zwei Grundfälle, und . Wir gehen davon aus, dass $f$

T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) .

$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n).$

T (0)

$T(0)$

T (1)

$T(1)$

, die wir später auch entspannen.

T (0) \leq T (1)

$T(0) \leq T(1)$

Ich behaupte, dass monoton ist und nicht abnimmt. Wir beweisen durch vollständige Induktion, dass . Dies ist für , also sei . Wir haben $T(n)$ $T(n+1) \geq T(n)$ $n = 0$ $n \geq 1$ Dies impliziert, dass Also, wenn

\begin{aligned} T (n + 1) & = T (⌊ (n + 1) / 2 ⌋) + T (⌈ (n + 1) / 2 ⌉) + f (n + 1) \\ \geq T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) = T (n) . \end{aligned}

$\begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*}$

T (2^{⌊ \log_{2} n ⌋}) \leq T (n) \leq T (2^{⌈ \log_{2} n ⌋}) .

$T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}).$

, wir sind fertig. Dies ist immer dann der Fall, wenn die Lösung für Zweierpotenzen die Form

T (2^{m}) = Θ (T (2^{m + 1}))

$T(2^m) = \Theta(T(2^{m+1}))$

T (n) = Θ (n^{a} \log^{b} n)

$T(n) = \Theta(n^a \log^b n)$

$T(0) \leq T(1)$ $T'$ $T'(0) = T'(1) = \min(T(0),T(1))$ $T'(n) \leq T(n)$ $T''$ $T''(0) = T''(1) = \max(T(0),T(1))$ $T(n) \leq T''(n)$ $T'=\Theta(h)$ $T''=\Theta(h)$ für die gleiche Funktion und damit auch . $h$ $T = \Theta(h)$

Lassen Sie uns nun die Annahme lockern, dass monoton ist. Angenommen, für eine monotone Funktion . Also für einige und groß genug. Der Einfachheit halber nehmen wir an, dass ; Der allgemeine Fall kann wie im vorherigen Absatz behandelt werden. Wiederum definieren wir zwei Wiederholungen indem wir durch ersetzen . Noch einmal, der Hauptsatz liefert dasselbe Ergebnis (bis zu konstanten Vielfachen), das auch mit dem identisch ist (bis zu konstanten Vielfachen), was wir erhalten würden, wenn wir die ursprüngliche Wiederholung nur mit Zweierpotenzen lösen würden. $f$ $f = \Theta(g)$ $g$ $cg(n) \leq f(n) \leq Cg(n)$ $c,C>0$ $n$ $n=0$ $T',T''$ $f$ $cg,Cg$

Yuval Filmus
quelle

Endlich muss ich das genauer lesen. Nett, danke! Ich dachte, ich würde dies für zukünftige Leser zur Kenntnis nehmen (weil ich darüber gestolpert bin): ist keine Einschränkung, da es nur für falsch ist Superpolynom und der Hauptsatz gilt nicht für solche.

T (2^{m}) \in Θ (T (2^{m + 1}))

$T(2^m) \in \Theta(T(2^{m+1}))$

T

$T$

Raphael

Ich habe versucht, Ihren Beweis detaillierter aufzuschreiben, und bin dabei festgefahren, Ihren letzten Satz zu beweisen. Insbesondere müssen wir zeigen, dass wir im selben Fall des Hauptsatzes für , und enden . Dies ist kein Problem für die Fälle 1 und 2, aber ich kann die Existenz von für Fall 3 nicht nachweisen (siehe Version in CLRS, S. 94 in der 3. Ausgabe). Haben Sie darüber nachgedacht oder haben Sie mit einer Version gearbeitet, die der Wikipedia ähnelt ?

c g

$cg$

f

$f$

C g

$Cg$

c < 1

$c < 1$

Raphael

Dies ist eine technische Tatsache. Wenn ist, verschwindet das Problem, siehe zum Beispiel users.encs.concordia.ca/~chvatal/notes/master.pdf . Die Funktion erfüllt automatisch die Bedingungen. Ich stelle mir vor, dass das Gleiche für und so weiter funktioniert . Alternativ können Sie diese Bedingung direkt auf und nicht auf : Es muss ein "reguläres" , das erfüllt .

f = Θ (n^{α})

$f = \Theta(n^\alpha)$

g

$g$

f = Θ (n^{α} \log^{β} n)

$f = \Theta(n^\alpha \log^\beta n)$

g

$g$

f

$f$

g

$g$

f = Θ (g)

$f = \Theta(g)$

Yuval Filmus

Nun, Sie haben behauptet, " monotone" sei eine ausreichende Bedingung (und ich habe Ihnen geglaubt), also habe ich versucht, damit zu arbeiten. Der in z. B. CLRS gegebene Hauptsatz gilt für z. B. , wenn ich mich nicht irre, so dass eine Beschränkung auf polylogarithmische Funktionen oder dergleichen nicht "technisch" ist, sondern das Ergebnis angemessen schwächt. Das Heben der "Regelmäßigkeit" nach hilft übrigens nicht: Ich habe sie bereits im entscheidenden Fall über die Regelmäßigkeit von / (nach Annahme). Also bin ich leider wieder bei meinem früheren Kommentar. Wenn dies wirklich nur technisch ist, sehe ich es nicht. Zu viele Ungleichungen.

g

$g$

f : n \mapsto 2^{n}

$f : n \mapsto 2^n$

g

$g$

c g

$cg$

C g

$Cg$

Raphael

Ich denke immer noch, dass es eine technische Sache ist. Der Zustand, um den Sie sich Sorgen machen, ist ein technischer Zustand. Für die meisten in der Praxis vorkommenden Funktionen gilt die Bedingung. Sie fragen nach der allgemeinsten Bedingung, unter der die obige Beweisskizze ausgeführt wird. Das ist eine interessante Frage, die ich nicht beantworten kann.

Yuval Filmus

Strenger Beweis für die Gültigkeit der Annahme

Antworten: