Estoy tratando de encontrar un límite para la siguiente ecuación de recurrencia:
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 ) .
Respuestas:
¡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 .ℓ≥0 3ℓ ℓ (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)
fuente
Puede usar el método más general Akra-Bazzi .
En su caso, necesitaríamos encontrar tal quep
(que dap≈1.364 )
y luego tenemos
Tenga en cuenta que realmente no necesita resolver la . Todo lo que necesitas saber es que 1 < p < 2 .p 1<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)
fuente
If we use the lower resp. upper bound as right-hand side of the recurrence, we getT′(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) .
fuente