Solução de equações de recorrência contendo duas chamadas de recursão

15

Estou tentando encontrar um $\Theta$ vinculado à seguinte equação de recorrência:

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$

Eu acho que o Teorema Mestre é inadequado devido à quantidade diferente de subproblemas e divisões. As árvores de recursão também não funcionam, pois não há ou melhor, . $T(1)$ $T(0)$

asymptotics recurrence-relation master-theorem Laura
fonte

5

Se você tiver uma recorrência desse formulário, DEVE haver um caso base, digamos

para todos os

. Caso contrário, não há como dizer o que a recorrência resolverá: talvez

para todos os

, onde

é o tamanho do problema original! (imagine uma recursão que termine comparando o número constante de tudo o que você está recorrendo a todos os subconjuntos dos elementos originais). Em outras palavras: nenhum caso básico implica informação insuficiente para resolver a recorrência.

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

Sim, as árvores de recursão ainda funcionam! Não importa se o caso base ocorre em ou ou ou mesmo . Também não importa qual é o valor real do caso base; seja qual for esse valor, é uma constante. $T(0)$ $T(1)$ $T(2)$ $T(10^{100})$

Visto através de grandes óculos Theta, a recorrência é . $T(n) = 2T(n/2)+T(n/3)+n^2$

A raiz da árvore de recursão tem o valor . $n^2$
A raiz tem três filhos, com valores , e . Assim, o valor total de todas as crianças é . $(n/2)^2$ $(n/2)^2$ $(n/3)^2$ $(11/18) n^2$
Verificação de sanidade: A raiz tem nove netos: quatro com valor , quatro com valor e um com valor . A soma destes valores é . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Uma prova de indução fácil implica que, para qualquer número inteiro , os nódulos ao nível têm valor total de . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
We conclude that $T(n) = \Theta(n^2)$ .

JeffE
fonte

14

You can use the more general Akra-Bazzi method.

In your case, we would need to find $p$ such that

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

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

(which gives $p \approx 1.364$ )

and we then have

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

Note that you don't really need to solve for $p$ . All you need to know is that $1 \lt p \lt 2$ .

A simpler method would be to set $T(x) = x^2 g(x)$ , and try proving that $g(x)$ is bounded.

Aryabhata
fonte

14

Let $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ be a shorthand for the right-hand side of the recurrence. We find an lower and upper bound for $f$ by using $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$

If we use the lower resp. upper bound as right-hand side of the recurrence, we get $T'(n) \in \Theta(n^2)$ in both cases by the Master theorem. Thus, $T(n)$ is bounded from above by $O(n^2)$ and from below by $\Omega(n^2)$ or, equivalently, $T(n) \in \Theta(n^2)$ .

For a complete proof, you should prove that $T$ is an increasing function.

Raphael
fonte

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

Solução de equações de recorrência contendo duas chamadas de recursão

Respostas: