Resolución de recurrencias con el método de sustitución

Question

Tengo varios problemas como este por hacer, pero me cuesta entender cómo se pasa de un paso al siguiente en el ejemplo (ver nota en la imagen). Si consigo entender este ejemplo creo que me irá bien. También quiero señalar que esto es sólo un ejemplo, no el problema de la tarea real.

Answer 1

Para dar una respuesta directa a su pregunta viene de la conjetura en el paso $(a)$ .

$T(n) = n \log_2 (n) + n$ es la suposición que hiciste en el paso $(a)$ . Usando ese reemplazo $n = \frac{n}{2}$ , $T(\frac{n}{2}) = \frac{n}{2} \log_2 (\frac{n}{2}) + \frac{n}{2}$ .

$T(\frac{n}{2}) = \frac{n}{2} (\log_2 (n) - \log_2(2)) + \frac{n}{2} = \frac{n}{2} \log_2 (n) - \frac{n}{2} + \frac{n}{2} = \frac{n}{2} \log_2 (n)$

Por lo tanto, $T(n) = 2 T(\frac{n}{2}) + n = 2 \frac{n}{2} \log_2 (n) + n = n \log_2 (n) + n$

Mientras resolvemos algunas recurrencias es bueno reconocer algunas cosas buenas sobre la recurrencia que estamos resolviendo. Por ejemplo, en esta recurrencia, observa que en cada paso estás dividiendo $n$ por $2$ . Así que estrictamente hablando a través de la recurrencia sólo se puede obtener $T(2^m)$ donde $m \in \mathbb{N}$ . Por ejemplo, $T(3)$ no puede obtenerse utilizando esta recurrencia. Sin embargo, tales recurrencias aparecen cuando se hacen ciertas cosas, cuando $n$ es realmente grande, utilizando recursivamente digamos un árbol binario. Cuando $n$ es realmente grande te interesa principalmente cómo se comporta la solución en un sentido asintótico y no la expresión precisa de la solución. En tales casos, se supone que $n=2^m$ por la simplicidad de los cálculos y el coste para todos $n$ (incluso cuando $n$ no es una potencia de $2$ ) puede demostrarse que obedece a la solución, obtenida mediante la hipótesis $n=2^m$ en sentido asintótico.

Si reescribiera la recurrencia en términos de $m$ y llame a $T(2^m) = S(m)$ entonces obtendríamos

$S(m) = 2 S(m-1) + 2^m$ desde $\frac{n}{2} = 2^{m-1}$ .

$S(m-1) = 2 S(m-2) + 2^{m-1}$ .

$S(m) = 4 S(m-2) + 2^m + 2^m$ y así sucesivamente (inducción oculta aquí) para obtener

$S(m) = 2^m S(0) + 2^m + 2^m + \cdots + 2^m + 2^m = m 2^m + 2^m$ .

Por lo tanto $T(n) = n \log_2(n) + n$ desde $n = 2^m$ es decir $m = \log_2(n)$

Answer 2

Como se suele decir, es una suposición. Si $T(n)=n lg n + n$ sólo sustituyes para conseguir el que pides "Hasta aquí". Así que la verdadera cuestión es si la inducción está justificada. La cuestión es que si la expresión para T es válida hasta n es válida hasta 2n (y tienes que explicar en este caso lo que ocurre para impar $n$ ) entonces es válido para todos $n$ .

Answer 3

Resuelve la siguiente relación de recurrencia mediante sustitución.

(i) $a_n = a_{n-1} + 5$ sujeta a la condición inicial $a_1 = 2$

(ii) $S_n = 5 S_{n-1}$ sujeta a la condición inicial $S_0 = 1$