poco ortodoxo solución de un caso especial del teorema maestro

Question

Estoy pidiendo referencias sobre un caso especial del teorema maestro. Este teorema aparece mucho en este sitio, animándome a estudiar en más detalle, por ejemplo, ver mis posts aquí y aquí. A mí me parece que tiene algunos casos especiales que voy a presentar a usted que puede ser tratada de una manera muy sencilla y sin la participación de maquinaria complicada. Este caso especial es aquella en la que el costo de la recursividad paso es $n$ y los subproblemas se obtiene dividiendo $n$ por los poderes de una sola y única prime.

Por ejemplo, tome $T(0) = 0$ y considerar la posibilidad de la recurrencia (el primer ser dos) $$T(n) = T(n/2) + 3 T(n/4) +n.$$

Vamos $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$

No es difícil ver que $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2} z -\frac{3}{4} z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k \etiqueta{1}.$$ Esta fórmula es exacta para todos los $n.$

Ahora tenemos $$[z^j] \frac{1}{1-\frac{1}{2} z -\frac{3}{4} z^2} = \frac{2}{\sqrt 13} \left( \left(\frac{1+\sqrt{13}}{4}\right)^{j+1} - \left(\frac{1-\sqrt {13}}{4}\right)^{j+1} \right) = \frac{2}{\sqrt{13}} \left(\rho_1^{j+1} - \rho_2^{j+1} \right), $$ donde hemos introducido $$\rho_{1,2} = \frac{1\pm\sqrt{13}}{4}.$$

Para obtener un límite inferior en $T(n)$, considere el caso de un uno seguido de ceros, dando $$ T(n) \ge \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) 2^{\lfloor \log_2 n \rfloor} = \frac{2^{\lfloor \log_2 n \rfloor+1}}{\sqrt{13}} \left( \frac{\rho_1^{\lfloor \log_2 n \rfloor+2}-1}{\rho_1-1} - \frac{\rho_2^{\lfloor \log_2 n \rfloor+2}-1}{\rho_2-1} \right) .$$ Este bound es realmente obtenidos.

Para un límite superior, considere el caso de una cadena de unos, $$ T(n) \le \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) \left(2^{\lfloor \log_2 n \rfloor+1}-2^j\right) \\ = \frac{2^{\lfloor \log_2 n \rfloor+2}}{\sqrt{13}} \left( \frac{\rho_1^{\lfloor \log_2 n \rfloor+2}-1}{\rho_1-1} - \frac{\rho_2^{\lfloor \log_2 n \rfloor+2}-1}{\rho_2-1} \right) -\frac{1}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left((2\rho_1)^{j+1} - (2\rho_2)^{j+1} \right).$$ El término correcto es $$-\frac{1}{\sqrt{13}} \left( \frac{(2\rho_1)^{\lfloor \log_2 n \rfloor+2}-1}{2\rho_1-1} - \frac{(2\rho_2)^{\lfloor \log_2 n \rfloor+2}-1}{2\rho_2-1} \right).$$ Esta obligado también es alcanzado. El spread entre el alto y bajo es un factor de $$ 2-2\frac{\rho_1-1}{2\rho_1-1}. $$

Tomando estos límites juntos, hemos demostrado que $$ T(n) \in \Theta \left( (2\rho_1)^{\lfloor \log_2 n \rfloor} \right) = \Theta \left( n 2^{\log_2 \rho_1 \log_2 n} \right) = \Theta \left( n \times n^{\log_2 \rho_1} \right) = \Theta \left(n^{1+\log_2 \rho_1} \right).$$ Este truco se generaliza para el caso de que el subproblem reducciones no son poderes de un único primer que dejo para el lector. Yo estaría feliz de ver referencias a la técnica que he presentado aquí. Yo soy esencialmente preguntando si es nuevo o no. Por lo que he visto el valor exacto de la exponente en la exponencial normalmente se deja sin tratar, mientras que los que he mostrado arriba que puede ser exacta. Diría usted que el uso de una generación de función para encapsular la mecánica del problema de la reducción de tamaño en la recurrencia es nuevo?

He aquí otro de los MSE de cálculo que utiliza el mismo método.

Answer 1

Un enfoque práctico es encontrar algunos hereditaria de los límites superior e inferior de $T(n)$ por múltiplos de potencias de $n$.

Si $T(n)=T(n/2)+3T(n/4)+n$, uno de los primeros centros de la recursividad mediante $S(n)=T(n)+cn$, luego $$ S(n)=S(n/2)-cn/2+3T(n/4)-3cn/4+n+cn=S(n/2)+3(n/4), $$ si $c=4$. A partir de ahora, $S(n)=T(n)+4n$.

Por lo tanto, el centrado de paso se basa en el afín parte de la recursividad, aquí $+n$.

Segundo, asumir que $S(k)\bowtie c k^a$ $k=n/2$ $k=3n/4$ $a\gt1$ donde $\bowtie$ es $\leqslant$ o $\geqslant$. A continuación,$S(n)\bowtie cn^a/2^a+c3n^a/4^a=(1/2^a+3/4^a)cn^a$. A partir de ahora, suponga que $a$ soluciona $$ \frac1{2^a}+\frac3{4^a}=1. $$ A continuación, la propiedad $S(n)\bowtie cn^a$ es hereditaria para todos los fijos $c$.

Por lo tanto, la potencia se basa en la parte lineal de la recursividad, aquí $T(n/2)+3T(n/4)$.

En particular, para algunos lo suficientemente pequeño como $c$ y algunos lo suficientemente grande como $C$, sostiene que $$ cn^a-4n\leqslant T(n)\leqslant Cn^a-4n, $$ para cada $n$. Desde $a\gt1$ en el presente caso, la contribución de la parte lineal de la recursividad gana por lo tanto, todo esto es más que suficiente para demostrar que $$ T(n)=\Theta(n^a). $$ Una cosa está clara, sin embargo, que es que el hecho de que $1/2$ $1/4$ son los inversos de los poderes de un único prime, que se invoca en la OP, no entra en la imagen. Sin embargo, para relacionarse $a$ a el exponente $\rho_1$ en el OP, suponga que $a=1+\log_2\rho$, luego $$ \frac1{2^a}+\frac3{4^a}=\frac1{2\rho}+\frac3{4\rho^2}, $$ por lo tanto $\rho$ resuelve $4\rho^2=2\rho+3$, $\rho=\frac14(1\pm\sqrt{13})$, como se reivindica en la OP.

Edit: Sobre el párrafo justificando la recompensa, me gustaría comprobar las referencias evidentes, es decir, generatingfunctionology y Flajolet libros.

Answer 2

Mira el Akra-Bazzi teorema, se da a los límites para las recurrencias como la suya. La prueba es un blizzard de integrales...