Hauptsatz nicht anwendbar?

Gegeben ist die folgende rekursive Gleichung

wir wollen den Hauptsatz anwenden und beachten, dass

$$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$

$$n^{\log_2(2)} = n.$$

Nun überprüfen wir die ersten beiden Fälle auf , dh ob$\varepsilon > 0$

• oder$n\log n \in O(n^{1-\varepsilon})$
• .$n\log n \in \Theta(n)$

Die beiden Fälle sind nicht erfüllt. Wir müssen also den dritten Fall überprüfen, nämlich ob

• .$n\log n \in \Omega(n^{1+\varepsilon})$

Ich denke, die dritte Bedingung ist auch nicht erfüllt. Aber wieso? Und was wäre eine gute Erklärung dafür, warum der Master-Satz in diesem Fall nicht angewendet werden kann?

Die drei Fälle des Master-Theorems, auf die Sie sich beziehen, sind in der Einführung in Algorithmen von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein (2. Auflage, 2001) .

Es wird richtig beobachtet, dass die fragliche Wiederholung zwischen Fall 2 und Fall 3 liegt. Das heißt, wächst schneller als n, aber langsamer als n 1 + & epsi ; für jedes & epsi ; > 0 .$f(n) = n \log n$$n$$n^{1+\varepsilon}$$\varepsilon > 0$

Der Satz kann jedoch verallgemeinert werden, um diese Wiederholung abzudecken. Erwägen

Fall 2A: Betrachten Sie für einige k ≥ $f(n) = \Theta (n^{\log_b a }\log_b^k n)$$k\geq 0$ .

Dieser Fall reduziert sich auf Fall 2, wenn . Es ist intuitiv klar, dass entlang jedes Zweigs des Wiederholungsbaums f ( x ) Θ ( log b n ) Mal hinzugefügt wird . Eine Skizze eines formelleren Beweises finden Sie unten. Das Endergebnis ist das$k = 0$$f(x)$$\Theta (\log_b n)$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$ .

In der Einführung in Algorithmen diese Aussage als Übung belassen.

Wenn wir diese Aussage auf die fragliche Wiederholung anwenden, erhalten wir schließlich

$$T(n) = \Theta(n \cdot \log^2 n).$$

Weitere Details zum Master-Theorem finden Sie auf der ausgezeichneten (imho) Wikipedia-Seite .

Da @sdcvvc in den Kommentaren darauf hinweist, dass Fall 3 hier nicht gilt, kann man sich auf die Regel von L'Hospital berufen, die besagt, dass für alle Funktionenf(x)undg(x), diein der Nähe voncdifferenzierbar sind. Angewandt auff(n)=nlognundg(n)=n1+εeindie zeigenkannlogn∉& THgr;(n1+ε)

$$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$$ $f(x)$$g(x)$$c$$f(n) = n \log n$$g(n) = n^{1+\varepsilon}$$\log n \not\in \Theta (n^{1+\varepsilon}).$

---

Skizze des Beweises des Hauptsatzes für Fall 2A.

Dies ist eine Reproduktion von Teilen des Beweises aus der Einführung in Algorithmen mit den erforderlichen Änderungen .

Zuerst beweisen wir das folgende Lemma.

Lemma A:

$$g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$$ where $h(n) = n^{\log_b a} \log_b^k n.$ Then $g(n) = n^{\log_b a} \log_b^{k +1} n.$

Proof: Substituting the $h(n)$ into the expression for $g(n)$ one can get

$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

If $n$ is an exact power of $b$ given a recurrence

$$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$$ one can rewrite it as $$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j T(n/b^j).$$ Substituting $f(n)$ with $\Theta(n^{\log_b a} \log_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.

The Akra-Bazzi theorem is a strict generalization of the master theorem. As a bonus its proof is a blizzard of integrals that will make your head spin ;-)

In any case, Sedgewick in his "Introduction to the analysis of algorithms" argues convincingly that one should strive to prove $T(n) \sim g(n)$ type asymptotics.