Wiederholung

8

Hinweis: Dies stammt aus JeffEs Algorithmen-Hinweisen zu Wiederholungen, Seite 5.

(1). Wir definieren also die Wiederholung ohne Basisfall. Jetzt verstehe ich, dass für die meisten Rezidive, da wir nach asymptotischen Grenzen suchen, der Basisfall keine Rolle spielen würde. Aber in diesem Fall sehe ich nicht einmal, wo wir den Basisfall definieren könnten. Gibt es eine Zahl, die wir garantiert treffen, wenn wir ausgehend von einer ganzen Zahl Quadratwurzeln ziehen? Definieren wir einfach für , für einige Realzahlen , ? $T(n) = \sqrt{n}T(\sqrt{n})+n$ $T(n) = a$ $n<b$ $a$ $b$

(2). Auf Seite 7 erhält Erickson, dass die Anzahl der Ebenen im Rekursionsbaum L erfüllt . Woher kommt das? Ich habe keine Ahnung. Ich sehe, dass die Anzahl der Blätter im Baum , aber ich habe keine Ahnung, wohin ich von dort aus gehen soll. $n^{{2}^{-L}} = 2$ $\sqrt(n)\sqrt(n) = n$

Jede Hilfe wird geschätzt!

Hinweise, die ich mir anschaue: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

recurrence-relation DB Cooper
quelle

7

Sie sollten wirklich eine dritte Frage stellen: Was passiert, wenn kein perfektes Quadrat ist ? Die Antwort auf diese Frage lautet, dass die tatsächliche Wiederholung oder anstelle von sollte Bei der Analyse werden nur Eingaben berücksichtigt, die "rekursive" Quadrate sind. $n$ $T(\lfloor \sqrt{n} \rfloor)$ $T(\lceil \sqrt{n} \rceil)$ $T(\sqrt{n})$

In Bezug auf Ihre erste Frage kann es mehr als einen Basisfall geben. Zum Beispiel ist vielleicht für alle . Sie werden garantiert irgendwann diesen Basisfall treffen. In diesem Fall beeinflusst, wie in den meisten Fällen, die genaue Form des Basisfalls nicht die großen Theta-Asymptotika (aber die verborgene Konstante). $T(n) = 1$ $n \leq 100$

Nehmen wir schließlich in Bezug auf Ihre zweite Frage an, dass Ihr Basisfall für angibt . Der Rekursionsbaum (der eine bestimmte Interpretation einiger Merkmale der Wiederholung darstellt) hat die folgende Form: $T(n)$ $n \leq C$

Die Wurzel ist eine Instanz der Größe . $n$
Die Wurzel hat die Instanzen der Größe . $\sqrt{n}$ $\sqrt{n}$
Jeder Knoten in Tiefe 1 hat Kinder, die Instanzen der Größe . $\sqrt{\sqrt{n}} = n^{1/4}$ $\sqrt{\sqrt{n}} = n^{1/8}$
Allgemeiner ist ein Knoten in der Tiefe eine Instanz der Größe . Sie können dies durch Induktion beweisen, indem Sie den Fall (wobei ) überprüfen und berechnen . $d$ $n^{1/2^d}$ $d = 0$ $n^{1/2^d} = n$ $\sqrt{n^{1/2^d}} = n^{1/2^{d+1}}$

Die Rekursion wird beendet , wenn die Instanz hat Größe höchstens , und dies geschieht , wenn . An dem Punkt, an dem dies geschieht, haben wir (unter der Annahme von ) und somit . Nehmen wir den Logarithmus, und so , was impliziert . Wir können daraus schließen, dass . Dies ist die Anzahl der Ebenen im Baum. Jeff verwendet , wodurch er seine spezielle Formel erhält. $C$ $n^{1/2^d} \leq C$ $n^{1/2^{d-1}} > C$ $n > C$ $\sqrt{C} < n^{1/2^d} \leq C$ $\frac{1}{2} \log C < \frac{\log n}{2^d} < \log C$ $\frac{\log n}{2^d} = \Theta(1)$ $2^d = \Theta(\log n)$ $d \approx \log\log n$ $C = 2$

Yuval Filmus
quelle

4

Beantwortung Ihrer ersten Frage. Alternativ zur Verwendung der Ober- und Untergrenze, um einen Basisfall zu erhalten, besteht eine Option darin, dass Sie die Form von annehmen können . $n$

Nehmen Sie zum Beispiel die Mergesort-Rekursion:

T (n) = 2 c \cdot T (\frac{n}{2}) + c \cdot n

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

Es ist klar, dass die meisten nicht gleichmäßig in ganze Zahlen geteilt werden. Es ist dann ziemlich üblich anzunehmen, dass die Form hat: $n$ $n$

n = 2^{k} k \in N

$n = 2^k \quad\quad k \in \mathbb{N}$

Dies impliziert, dass jedes eine positive Potenz von , wodurch unser Basisfall immer auf . Alternativ könnten wir den Basisfall anstelle von indem wir annehmen, dass die Form hat: $n$ $2$ $1$ $c$ $1$ $n$

n = c \cdot 2^{k} k \in N, c \in N^{+}

$n = c \cdot 2^k \quad\quad k \in \mathbb{N}, c \in \mathbb{N}^+$

Wir können dies auf unsere Wiederholung anwenden:

T (n) = \sqrt{n} \cdot T (\sqrt{n}) + n

$T(n) = \sqrt{n} \cdot T\left(\sqrt{n}\right) + n$

Angenommen, hat die Form: Dann wird der Basisfall immer in eine Konstante . $n$

n = c^{2^{k}} k \in N, c \in N^{+}

$n = c^{2^k} \quad \quad k \in \mathbb{N}, c \in \mathbb{N}^+$

c

$c$

Wenn Sie dies unter dieser Annahme beweisen können, können Sie einen Beweis für Werte erstellen , die diese Form nicht haben. Ein Ansatz wäre der Versuch, ihn an das nächsthöhere (oder niedrigste) zu binden , das diese Form hat. $n$ $n$

Ryan
quelle

Wiederholung

Antworten: