relación de recurrencia $f(n)=5f(n/2)-6f(n/4) + n$

Question

He estado tratando de resolver a esta relación de recurrencia para una semana, pero no he subido con una solución.

$f(n)=5f(n/2)-6f(n/4) + n$

Resolver esta relación de recurrencia para $f(1)=2$ y $f(2)=1$

En primera vista parece una división y conquistar la ecuación, pero la $6f(n/4)$ me confunde. Por favor me ayude a encontrar una solución. Atentamente

Answer 1

Sólo puede definir $f(2^k)$. (Intente definir $f(3)$. Es imposible). Por lo tanto hacer la transformación $$ n = 2 ^ k, \quad \text{and definir} \quad g(k)=f(2^k). $$ De $g$ tienes que $$ g (0) = 2, \quad g (1) = 1\quad g de \text{and}\quad (k + 2) = 5 g(k+1) - 6 g (k) + 2 ^ {k + 2}. $$ Si $2^{k+2}$ no estaba allí, entonces $g$ tendría que ser de la forma $g(k)=c_12^k+c_23^k$. Con este término adicional la solución general de la relación recursiva es el % de forma $g(k)=c_12^k+c_23^k+c_3k2^k$. Acaba de encontrar los valores de las constantes.

Answer 2

Supongamos que empezar por la solución de la siguiente recurrencia: $$T(n) = 5 T(\lfloor n/2 \rfloor) - 6 T(\lfloor n/4 \rfloor) + n$$ donde $T(0) = 0.$ Ahora vamos a $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ ser la representación binaria de $n.$ Extendemos la recursividad para obtener una exacta fórmula para todas las $n:$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Observar que las raíces de $$1-\frac{5}{2}z+\frac{6}{4} z^2 \quad\text{se}\quad\rho_0=1\quad\text{y}\quad\rho_1=\frac{2}{3}.$$ De ello se desprende que los coeficientes de la racional plazo tienen la forma $$c_0 + c_1 \left(\frac{3}{2}\right)^j.$$ En realidad, la solución para $c_{0,1}$ obtenemos la fórmula $$[z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2} = 3 \left(\frac{3}{2}\right)^j - 2.$$ Esto le da la exacta fórmula para $T(n):$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j - 2\right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ Ahora, para un límite superior en este considere una cadena de uno de los dígitos, lo que da $$T(n)\le \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j - 2\right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = \frac{27}{2} \times 3^{\lfloor \log_2 n \rfloor} - (12+4\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor} -\frac{1}{2}.$$ Límite inferior considerar un uno seguido por una cadena de ceros, lo que da $$T(n)\ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j - 2\right) 2^{\lfloor \log_2 n \rfloor} = 9 \times 3^{\lfloor \log_2 n \rfloor} - (8+2\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor}.$$ Unir los dos límites se sigue que $T(n)$ es asintótica de la siguiente manera: $$T(n)\in\Theta\left(3^{\lfloor \log_2 n \rfloor}\right) = \Theta(2^{\log_2 n \times \log_2 3}) = \Theta(n^{\log_2 3})$$ con el coeficiente inicial entre el $9/2$ $9.$ Ahora se supone que vamos a tener $f(0)=0$, $f(1)=2$, y $f(2)=1,$ a fin de comenzar con $$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} - 2\right) 2^{\lfloor \log_2 n \rfloor}.$$ Esto es igual a dos a $n=1$ pero igual a doce en $n=2$, por lo que necesitamos un aporte adicional de $$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} - 2\right) 2^{\lfloor \log_2 n \rfloor} - 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor-1} - 2\right) 2^{\lfloor \log_2 n \rfloor-1}.$$ Esto se simplifica a (de $n\ge 2$) $$ T(n) + 3^{\lfloor \log_2 n \rfloor+1} -2^{\lfloor \log_2 n \rfloor+1} - 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times \left(3^{\lfloor \log_2 n \rfloor} -2^{\lfloor \log_2 n \rfloor}\right).$$ El comportamiento de aquí es muy desigual, pero la fórmula es exacta y el orden de crecimiento sigue siendo el mismo. Aquí hay otro Maestro Teorema de la computación en el MSE.