Klärung der Nachweis mit der Regelmäßigkeit Zustand Master Theorem

Question

Ich wollte den text Einführung in Algorithmen von Cormen et al.Wo stieß ich auf die folgende Aussage in dem Nachweis der Dritte Fall des Master-Theorems.

(Die Anweisung von Master-theorem) Lassen $a \geqslant 1$ und $b > 1$ Konstanten, lassen Sie $f(n)$ eine Funktion, und lassen Sie $T (n)$ definiert werden, auf die nicht negativen ganzen zahlen, die durch die Wiederholung( die Rekursion teilt ein problem der Größe $n$ in $a$ Probleme der Größe $n/b$ jede und nimmt $f(n)$ für das aufteilen und vereinen)

$T(n) = aT(n/b)+ f (n)$ ;

wo wir interpretieren $n/b$ bedeutet entweder $\lceil b/n ceil$ oder $\lfloor b/n floor$.Dann $T(n)$ hat folgende asymptotische Schranken:

1. Wenn $f(n)=O (n^{\log_ba - \epsilon})$ für einige Konstante $\epsilon > 0$, dann $T(n)= heta (n^{\log_ba})$.

2. Wenn $f(n)= heta (n^{\log_ba})$, dann $T(n)= heta (n^{\log_ba}\lg n)$

3. Wenn $f(n)=\Omega (n^{\log_ba + \epsilon})$ für einige Konstante $\epsilon > 0$, und wenn $af(n/b) \leqslant cf(n)$ für einige Konstante $c < 1$ und alle hinreichend großen n, dann $T(n)= heta (f(n))$.

Für $n$ als genauen Befugnisse der $b$ wir beschränken die Domäne von T(n) wie folgt:

$$T(n)= heta(1), n=1$$ $$T(n)=aT(n/b)+f(n) ,n=b^i$$

Jetzt im Beweis des Master-Theorems mit $n$ wie genau macht der $b$ der Ausdruck für $T(n)$ reduziert auf :

$$T(n)= heta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Dann die Autoren übernehmen Sie die folgenden,

$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Dann für den Nachweis der 3. Fall des Master-Theorems die Autoren beweisen Sie das folgende lemma,

Lemma 1 :Wenn $a\cdot f(n/b)\leqslant c\cdot f(n)$ für einige Konstante $c<1$ und für alle $n\geqslant b$ dann $g(n)= heta(f(n))$

Sie sagen, dass:

unter Ihrer Annahme, dass $c<1$ und $n \geqslant b$Sie haben $a \cdot f(n/b)\leqslant c \cdot f(n) \impliziert f(n/b)\leqslant (c/a) \cdot f(n)$

dann Iteration $j$ mal Erträge, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$

Ich konnte nicht Recht bekommen, die Mathematik hinter Iteration $j$ mal.

Außerdem konnte ich nicht ganz die Logik, die hinter der Annahme der $n\geqslant b$ für die situation, $n$ sollte ausreichend groß sein.(Als der Dritte Fall der Master-Theorem besagt, dass.)

Der Beweis von lemma wie folgt fortgesetzt:

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n)$$ So, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$ $$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$ $$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ als $c<1$ wir haben eine unendliche geometrische Reihe $$= f(n) \left(\frac{1}{1-c} ight)$$ $$=O(f(n))$$ als $c$ ist eine Konstante.(Beachten Sie, dass $T(n)=\Omega(f(n))$ aus der Rekursion Diagramm.)

Dann die Autoren der Nachweis der Dritte Fall des Master-Theorems für $n$ wie genau macht der $b$:

Lemma 2:Lassen Sie $a \geqslant 1$ und $b>1$, wenn $f(n)=\Omega (n^{\log_ba + \epsilon})$ für einige Konstante $\epsilon > 0$, und wenn $af(n/b) \leqslant cf(n)$ für einige Konstante $c < 1$ und alle hinreichend großen n, dann $T(n)= heta (f(n))$.

So $$T(n) = heta(n^{\log_ba}) + g(n) = heta(n^{\log_ba}) + heta(f(n)) = heta(f(n))$$ als $f(n)=\Omega (n^{\log_ba + \epsilon})$

Darüber hinaus sind in den ähnlichen Beweis für den Dritten Fall der Allgemeinen master-theorem (nicht vorausgesetzt $n$ als genauen Befugnisse der $b$) gibt es wieder das Buch wird davon ausgegangen, dass $n\geqslant b+b/(b-1)$ gehen Sie mit der situation genügend großer $n$.

Ich verstehe nicht ganz, was die bestimmten Wert zu tun hat und warum eine solche wird davon ausgegangen, wie ausreichend große $n$

(Ich habe nicht die details der zweiten situation, wie ich fühle, dass es muss etwas sein, ähnlich wie in der ersten situation, aber es kann gefunden werden hier)

Answer 1

Beginnen wir mit dem Problem der iteration.Angenommen, eine Funktion $f$ erfüllt $$ f(n/b) \leq (c/a)f(n).$$ Dann wird es auch erfüllt $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n).$$ Beweisen Sie durch Induktion, dass für alle ganzzahligen $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n).$$

Wie für Ihre zweite Frage, zu der Annahme, dass $n$ ist groß genug:der Beweis ist einfach nur schlampig.Sie können nicht davon ausgehen, dass $f(n/b) \leq (c/a) f(n)$ gilt für alle $n \geq b$.In der Tat, in Introduction to algorithms, third edition, Sie tun nicht machen eine solche Annahme für den Fall, wo $n$ ist eine Potenz von $b$.

Sie scheinen zu machen, wie die Annahme im Falle der Allgemeinen $n$, ist , aber was Sie wirklich sagen, ist, dass die Ungleichheit $f(\lceil n/b ceil) \leq (c/a) f(n)$ macht nur Sinn für $n \ge b + b/(b-1)$.Mit der Idee der Nachweis der besonderen Fall, wo $n$ ist eine Potenz von $b$, vervollständigen Sie den Beweis für den Allgemeinen Fall.Ich würde jedoch stark empfehlen ignorieren solche Technik zu präsentieren.Das master-theorem ist im wesentlichen eine Berechnung, und Sie können darauf Vertrauen die Autoren, dass es funktioniert.Nichts Interessantes verborgen ist, unter den Teppich.