Lösen von Rekursionsgleichungen mit zwei Rekursionsaufrufen

15

Ich versuche, eine $\Theta$ Grenze für die folgende Wiederholungsgleichung zu finden:

T (n) = 2 T (n / 2) + T (n / 3) + 2 n^{2} + 5 n + 42

$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$

Ich denke, der Hauptsatz ist aufgrund der unterschiedlichen Anzahl von Teilproblemen und Unterteilungen ungeeignet. Auch Rekursionsbäume funktionieren nicht, da es kein $T(1)$ bzw. $T(0)$ .

asymptotics recurrence-relation master-theorem Laura
quelle

5

Wenn Sie eine Wiederholung dieser Form haben, MUSS es einen Basisfall geben, sagen Sie

für alle

. Wenn nicht, gibt es keine Ahnung, wie sich die Wiederholung auswirkt: Vielleicht ist

für alle

, wobei

die Größe des ursprünglichen Problems ist! (Stellen Sie sich eine Rekursion vor, bei der Sie die konstante Anzahl der Rekursionen mit allen Teilmengen der ursprünglichen Elemente vergleichen.) Mit anderen Worten: Kein Basisfall impliziert nicht genügend Informationen, um die Rekursion zu lösen.

T (n) \leq 42

$T(n) \leq 42$

n < 100

$n < 100$

T (n) = 2^{m}

$T(n) = 2^m$

n < 100

$n < 100$

m

$m$

Alex ten Brink

15

Ja, Rekursionsbäume funktionieren immer noch! Es spielt keine Rolle, ob der Basisfall bei oder oder oder sogar auftritt . Es spielt auch keine Rolle, wie hoch der tatsächliche Wert des Basisfalls ist. Was auch immer dieser Wert ist, es ist eine Konstante. $T(0)$ $T(1)$ $T(2)$ $T(10^{100})$

Durch Big-Theta-Brillen gesehen ist die Wiederholung . $T(n) = 2T(n/2)+T(n/3)+n^2$

Die Wurzel des Rekursionsbaums hat den Wert . $n^2$
Die Wurzel hat drei Kinder mit den Werten , und . Somit ist der Gesamtwert aller Kinder . $(n/2)^2$ $(n/2)^2$ $(n/3)^2$ $(11/18) n^2$
Sanity Check: Die Wurzel hat neun Enkelkinder: vier mit Wert , vier mit Wert und eines mit Wert . Die Summe dieser Werte ist . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Ein einfacher Induktions Nachweis bedeutet , daß für jede ganze Zahl , die Knoten auf der Stufe Gesamtwert . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
Die Niveausummen bilden eine absteigende geometrische Reihe, daher ist nur der größte Term . $\ell=0$
Wir schließen daraus, dass . $T(n) = \Theta(n^2)$

JeffE
quelle

14

Sie können die allgemeinere Akra-Bazzi- Methode anwenden .

In Ihrem Fall müssten wir so finden, dass $p$

\frac{1}{2^{p - 1}} + \frac{1}{3^{p}} = 1

$\frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$

(was ergibt ) $p \approx 1.364$

und dann haben wir

T (x) = Θ (x^{p} + x^{p} \int_{1}^{x} t^{1 - p} d t) = Θ (x^{2})

$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$

Beachten Sie, dass Sie für nicht wirklich lösen müssen . Alles was Sie wissen müssen ist, dass . $p$ $1 \lt p \lt 2$

Eine einfachere Methode wäre, und zu beweisen, dass begrenzt ist. $T(x) = x^2 g(x)$ $g(x)$

Aryabhata
quelle

14

Sei eine Abkürzung für die rechte Seite der Wiederholung. Wir finden eine untere und obere Grenze für unter Verwendung von : $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ $f$ $T(n/3) \leq T(n/2)$

3 T (n / 3) + 2 n^{2} + 5 n + 42 \leq f (n) \leq 3 T (n / 2) + 2 n^{2} + 5 n + 42

$3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$

$T'(n) \in \Theta(n^2)$ $T(n)$ $O(n^2)$ $\Omega(n^2)$ $T(n) \in \Theta(n^2)$

Für einen vollständigen Beweis sollten Sie das beweisen $T$ ist eine zunehmende Funktion.

Raphael
quelle

let us continue this discussion in chat

Raphael

1

That trick won't work for similar recurrences, like

T (n) = 2 T (n / 2) + 3 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 3T(n/3) + n^2$ , that can be solved with recursion trees. (But even recursion trees won't work for

T (n) = 2 T (n / 2) + 4 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 4T(n/3) + n^2$ , which can be solved with Akra-Bazzi.)

JeffE

Lösen von Rekursionsgleichungen mit zwei Rekursionsaufrufen

Antworten: