Rozwiązywanie równań rekurencyjnych zawierających dwa wezwania rekurencyjne

15

Próbuję znaleźć granicę $\Theta$ dla następującego równania rekurencyjnego:

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$

Uważam, że Twierdzenie Mistrza jest nieodpowiednie ze względu na różną liczbę podproblemów i podziałów. Również drzewa rekurencyjne nie działają, ponieważ nie ma a raczej . $T(1)$ $T(0)$

asymptotics recurrence-relation master-theorem Laura
źródło

5

Jeśli masz powtarzalność tego formularza, MUSI istnieć przypadek podstawowy, powiedzmy

dla wszystkich

. Jeśli nie, to nie ma mowy o rozwiązaniu problemu: może

dla wszystkich

, gdzie

jest rozmiarem pierwotnego problemu! (wyobraź sobie rekurencję, która kończy się porównywaniem stałej liczby wszystkiego, co rekursujesz, ze wszystkimi podzbiorami oryginalnych elementów) Innymi słowy: żaden przypadek podstawowy nie sugeruje wystarczającej ilości informacji do rozwiązania tej rekurencji.

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

Tak, drzewa rekurencyjne nadal działają! Nie ma znaczenia, czy w ogóle występuje, w przypadku podstawy i i , a nawet . Nie ma również znaczenia, jaka jest rzeczywista wartość przypadku podstawowego; niezależnie od tej wartości, jest stała. $T(0)$ $T(1)$ $T(2)$ $T(10^{100})$

Widziana przez okulary Big-Theta, nawrót wynosi . $T(n) = 2T(n/2)+T(n/3)+n^2$

Korzeń drzewa rekurencyjnego ma wartość . $n^2$
Rdzeń ma troje potomków o wartościach , i . Zatem, całkowita wartość wszystkich dzieci jest . $(n/2)^2$ $(n/2)^2$ $(n/3)^2$ $(11/18) n^2$
Sprawdzanie rozsądku: Rdzeń ma dziewięciu wnuków: czterech o wartości , czterech o wartości i jednego o wartości . Suma tych wartości jest . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Łatwe dowód indukcji wskazuje, że dla każdej liczby całkowitej , że węzły na poziomie mieć całkowitą wartość . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
Kwoty poziom tworzą opadającą geometrycznym, więc tylko największym termin spraw. $\ell=0$
Wnioskujemy, że . $T(n) = \Theta(n^2)$

JeffE
źródło

14

Możesz użyć bardziej ogólnej metody Akra-Bazzi .

W twoim przypadku musielibyśmy znaleźć takie $p$

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

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

(co daje ) $p \approx 1.364$

i wtedy mamy

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)$

Zauważ, że tak naprawdę nie musisz rozwiązywać problemów z . Wszystko, co musisz wiedzieć, to że . $p$ $1 \lt p \lt 2$

Prostszą metodą byłoby ustawienie i próba udowodnienia, że jest ograniczone. $T(x) = x^2 g(x)$ $g(x)$

Aryabhata
źródło

14

Niech będzie skrótem dla prawej strony nawrotu. Znajdujemy dolną i górną granicę dla , stosując : $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$

Jeśli użyjemy niższej lub niższej. górną granicę jako prawą stronę nawrotu, otrzymujemy w obu przypadkach przez twierdzenie Master. Zatem jest ograniczony od góry przez a od dołu przez lub, równoważnie, . $T'(n) \in \Theta(n^2)$ $T(n)$ $O(n^2)$ $\Omega(n^2)$ $T(n) \in \Theta(n^2)$

Aby uzyskać pełny dowód, powinieneś udowodnić, że jest funkcją rosnącą. $T$

Raphael
źródło

niech nam kontynuować tę dyskusję w czacie

Raphael

1

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

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

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

$T(n) = 2T(n/2) + 4T(n/3) + n^2$ , które można rozwiązać za pomocą Akra-Bazzi.)

JeffE

Rozwiązywanie równań rekurencyjnych zawierających dwa wezwania rekurencyjne

Odpowiedzi: