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

15

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

T(n)=2T(n/2)+T(n/3)+2n2+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 ( 0 ) .T(1)T(0)

Laura
fonte
5
Se você tiver uma recorrência desse formulário, DEVE haver um caso base, digamos para todos os n < 100 . Caso contrário, não há como dizer o que a recorrência resolverá: talvez T ( n ) = 2 m para todos os n < 100 , onde m é 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)42n<100T(n)=2mn<100m
Alex ten Brink

Respostas:

15

Sim, as árvores de recursão ainda funcionam! Não importa se o caso base ocorre em ou T ( 1 ) ou T ( 2 ) ou mesmo T ( 10 100 ) . 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(10100)

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

  • A raiz da árvore de recursão tem o valor .n2

  • A raiz tem três filhos, com valores , ( n / 2 ) 2 e ( n / 3 ) 2 . Assim, o valor total de todas as crianças é ( 11 / 18 de ) N 2 .(n/2)2(n/2)2(n/3)2(11/18)n2

  • Verificação de sanidade: A raiz tem nove netos: quatro com valor , quatro com valor ( n / 6 ) 2 e um com valor ( n / 9 ) 2 . A soma destes valores é ( 11 / 18 de ) 2 n 2 .(n/4)2(n/6)2(n/9)2(11/18)2n2

  • Uma prova de indução fácil implica que, para qualquer número inteiro , os 3 l nódulos ao nível têm valor total de ( 11 / 18 de ) N 2 .03(11/18)n2

  • The level sums form a descending geometric series, so only the largest term =0 matters.

  • We conclude that T(n)=Θ(n2).

JeffE
fonte
14

You can use the more general Akra-Bazzi method.

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

12p1+13p=1

(which gives p1.364)

and we then have

T(x)=Θ(xp+xp1xt1pdt)=Θ(x2)

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

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

Aryabhata
fonte
14

Let f(n)=2T(n/2)+T(n/3)+2n2+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)T(n/2):

3T(n/3)+2n2+5n+42f(n)3T(n/2)+2n2+5n+42

If we use the lower resp. upper bound as right-hand side of the recurrence, we get T(n)Θ(n2) in both cases by the Master theorem. Thus, T(n) is bounded from above by O(n2) and from below by Ω(n2) or, equivalently, T(n)Θ(n2).


  1. For a complete proof, you should prove that T is an increasing function.
Raphael
fonte
1
That trick won't work for similar recurrences, like T(n)=2T(n/2)+3T(n/3)+n2, that can be solved with recursion trees. (But even recursion trees won't work for T(n)=2T(n/2)+4T(n/3)+n2, which can be solved with Akra-Bazzi.)
JeffE