Resolver la relación de recurrencia $T(n)=2T(n/4)+\sqrt{n}$

Question

He resuelto $T(n)=2T(n/4)+\sqrt{n}$ a la igualdad de $2^{\log_{4}n}(\log_{4}n+1)$, pero no estoy seguro de cómo resolverlo directamente.

Tengo:

$2(2T(\frac{n}{16})+\sqrt{\frac{n}{4}})+\sqrt{n} = 4T(\frac{n}{16})+2\sqrt{n}$

$2(4T(\frac{n}{64})+2\sqrt{\frac{n}{16}})+\sqrt{n} = 8T(\frac{n}{64})+2\sqrt{n}$

$2(8T(\frac{n}{256})+2\sqrt{\frac{n}{64}})+\sqrt{n}=16T(\frac{n}{256})+\frac{5}{4}\sqrt{n}$

Yo no soy de ver un patrón aquí y yo no estoy seguro de que estoy modificando $n$ según sea necesario. ¿Cuál es el problema?

Answer 1

Veamos la ecuación de $T(n) = 2 T(n/4) + \sqrt{n}$ en una ecuación de recurrencia. Para este fin, vamos a $f(m) = T(4^m p)$ algunos $p>0$. Entonces $$f(m) = 2 f(m-1) + \sqrt{p} 2^m$$ que pueden ser sistemáticamente resuelto. Primero que volver a escribir como $$2^{m} f(m) - 2^{-(m-1)} f(m-1) = \sqrt{p}$$ A continuación, la suma de las ecuaciones de $m=1$ a algunos límite superior $k$: $$\sum_{m=1}^k \left(2^{m} f(m) - 2^{-(m-1)} f(m-1) \right) = \sum_{k=1}^m \sqrt{p}$$ La suma en el lado izquierdo de telescopios: $$\begin{eqnarray} \sum_{m=1}^k \left(2^{-m} f(m) - 2^{-(m-1)} f(m-1) \right) &=& \left(2^{-m} f(m) - \color\green{2^{-(m-1)} f(m-1)}\right) + \\ &\phantom{=}& \left(\color\green{2^{-(m-1)} f(m-1)} - 2^{-(m-2)} f(m-2)\right) + \\ &\phantom{=}& \vdots \\ &\phantom{=}& \left( 2^{-2} f(2) - \color\green{2^{-1} f(1)} \right) +\\ &\phantom{=}& \left( \color\green{2^{-1} f(1)} - 2^{-0} f(0) \right) \\ &=& 2^{-m} f(m) - f(0) \end{eqnarray}$$ Por lo tanto, llegamos a la solución $$f(m) = 2^m \left( m \sqrt{p} + f(0) \right)$$ desde $m = \log_4 \left(\frac{n}{p}\right)$ obtenemos: $$T(n) = \sqrt{\frac{n}{p}} \left( \sqrt{p} \cdot \log_4 \frac{n}{p} + f(0)\right) = \sqrt{n} \log_4(n) + d \sqrt{n}$$ donde $d$ es una conexión constante a ser determinado por la condición inicial.

Answer 2

Hay otra estrechamente relacionada con la recurrencia que admite una exacta solución. Supongamos que tenemos $T(0)=0$ $n\ge 1$ (esto le da $T(1)=1$) $$T(n) = 2 T(\lfloor n/4 \rfloor) + \lfloor \sqrt{n} \rfloor.$$

Además vamos a la base de cuatro representación de $n$ ser $$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$

Entonces podemos desenrollar la recurrencia para obtener la siguiente exacta fórmula para $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j\Bigg\lfloor \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}} \Bigg\rfloor.$$

Ahora para obtener un límite superior considere una cadena de dígitos con valor de tres para obtener

$$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} 3\times 4^{k-j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j} -1} \\ < \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} \sqrt{4^{\lfloor \log_4 n \rfloor +1}} \\ = (\lfloor \log_4 n \rfloor + 1) \times 2^{\lfloor \log_4 n \rfloor +1}.$$

Este bound es realmente alcanzado y no pueden ser mejorados, como el límite inferior, que se produce con un dígito, seguido por ceros a dar $$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor-j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} \sqrt{4^{\lfloor \log_4 n \rfloor}} \\ = (\lfloor \log_4 n \rfloor + 1) \times 2^{\lfloor \log_4 n \rfloor}.$$

Unirse a la dominante en términos de la parte superior y el límite inferior obtenemos el asymptotics $$\lfloor \log_4 n \rfloor \times 2^{\lfloor \log_4 n \rfloor} \en \Theta\left(\log_4 n \times 4^{1/2 \log_4 n}\right) = \Theta\left(\log n \times \sqrt{n}\right).$$

Observar que no hay un orden menor plazo $$2^{\lfloor \log_4 n \rfloor} \en \Theta\left(4^{1/2 \log_4 n}\right) = \Theta\left(\sqrt{n}\right).$$

Lo anterior es de acuerdo con lo que el Maestro teorema se iba a producir.

Anexo 3 De Noviembre De 2014. El límite inferior es la falta de un orden menor plazo, que es $-(2^{\lfloor \log_4 n \rfloor+1}-1)$ el mismo que se ha hecho en este MSE enlace.

Aquí es otro cálculo en el mismo espíritu: MSE enlace.