Express $T(n) $ como una relación de recurrencia y derivar una expresión para $T(n)$ en términos de $n$ .

Question

Pregunta:

$T(n)$ resuelve el problema dividiéndolo en 4 subproblemas del mismo tipo, cada uno de tamaño $n/4$ . La solución del problema original se obtiene combinando las soluciones del $4$ subproblemas en el tiempo $ n$ . Express $T(n) $ como una relación de recurrencia y derivar una expresión para $T(n)$ en términos de $n$ Asumir $T(1) = 2$ .

Relación de recurrencia:

$\frac{2}4 +\frac{2}4+\frac{2}4+\frac{2}4$ $$T(2)=2$$ $\frac{3}4 +\frac{3}4+\frac{3}4+\frac{3}4$ $$T(3)=3$$ $\frac{4}4 +\frac{4}4+\frac{4}4+\frac{4}4$ $$T(4)=4$$ $$T(n)=T(n-1)+1$$ $$T(n)=n$$ para $n 2$

¿Qué precisión tiene la relación recursiva y la expresión para $T(n)$ ¿en relación con la cuestión que nos ocupa?

Answer 1

Vuelve a leer las dos primeras frases. El objetivo de los algoritmos de divide y vencerás es tomar un gran problema y dividirlo en otros más pequeños. $T(n)$ es el tiempo para resolver un problema de tamaño $n$ . ¿De qué tamaño son los problemas más pequeños que se cortan? $T(that)$ es el tiempo para resolver cada uno de los problemas más pequeños. Luego hay que combinar las soluciones más pequeñas en una solución de tamaño $n$ . Te dicen el tiempo que tarda. ¿Ayuda eso a escribir la recurrencia? Podrías revisar la derivación de tu texto del tiempo requerido para la ordenación, que corta el problema en dos mitades. El enfoque es similar: el objetivo de este problema es ver si lo has entendido.

Añadido: Como se divide el problema en cuatro cuartos, la resolución de los cuartos requiere $4T(\frac n4)$ . Entonces toma $n$ para combinarlos, por lo que tenemos $$T(n)=4T(\frac n4)+n$$