Resolver ecuaciones de recurrencia que contienen dos llamadas de recursión

15

Estoy tratando de encontrar un límite para la siguiente ecuación de recurrencia:Θ

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

Me imagino que el teorema maestro es inapropiado debido a la cantidad diferente de subproblemas y divisiones. Además, los árboles de recursión no funcionan ya que no hay o más bien T ( 0 )T(1)T(0) .

Laura
fuente
55
Si tiene una recurrencia de esa forma, DEBE haber un caso base, digamos para todos los n < 100 . Si no, entonces no hay forma de decir a qué se resolverá la recurrencia: tal vez T ( n ) = 2 m para todos n < 100 , ¡donde m es el tamaño del problema original! (imagine una recursión que termina en la comparación del número constante de lo que sea que esté recurriendo a todos los subconjuntos de los elementos originales) En otras palabras: ningún caso base implica que no hay suficiente información para resolver la recurrencia. T(n)42n<100T(n)=2mn<100m
Alex ten Brink

Respuestas:

15

¡Sí, los árboles de recursión todavía funcionan! No importa en absoluto si el caso base ocurre en o T ( 1 ) o T ( 2 ) o incluso T ( 10 100 )T(0)T(1)T(2)T(10100) . Tampoco importa cuál sea el valor real del caso base; cualquiera que sea ese valor, es una constante.

Visto a través de lentes big-Theta, la recurrencia es .T(n)=2T(n/2)+T(n/3)+n2

  • La raíz del árbol de recursión tiene valor .n2

  • La raíz tiene tres hijos, con valores , ( n / 2 ) 2 y ( n / 3 ) 2 . Por lo tanto, el valor total de todos los niños es ( 11 / 18 ) n 2 .(n/2)2(n/2)2(n/3)2(11/18)n2

  • Comprobación de cordura: la raíz tiene nueve nietos: cuatro con valor , cuatro con valor ( n / 6 ) 2 y uno con valor ( n / 9 ) 2 . La suma de estos valores es ( 11 / 18 ) 2 n 2 .(n/4)2(n/6)2(n/9)2(11/18)2n2

  • Una prueba de inducción fácil implica que para cualquier entero , los 3 l nodos a nivel tienen valor total ( 11 / 18 ) n 2 .03(11/18)n2

  • Las sumas de nivel forman una serie geométrica descendente, por lo que solo el término más grande importa= 0 .=0

  • Concluimos que .T(n)=Θ(n2)

JeffE
fuente
14

Puede usar el método más general Akra-Bazzi .

En su caso, necesitaríamos encontrar tal quep

12p1+13p=1

(que da p1.364 )

y luego tenemos

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

Tenga en cuenta que realmente no necesita resolver la . Todo lo que necesitas saber es que 1 < p < 2 .p1<p<2

Un método más simple sería establecer e intentar probar que g ( x ) está acotada.T(x)=x2g(x)g(x)

Aryabhata
fuente
14

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
fuente
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