Diferencia entre revisiones de «Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Recursividad/Solución al ejercicio 3 de recursividad»

Contenido eliminado Contenido añadido
Rgfernan (discusión | contribs.)
Nueva página: Calculando la complejidad del algoritmo recursivo. En este caso, el algoritmo abre 4 hijos, pero y la complejidad general para un algoritmo que abra n hijos es: <math>C = \cfrac{n^{h...
 
Rgfernan (discusión | contribs.)
Sin resumen de edición
Línea 8:
<math>C = \cfrac{4^{h+1} - 1}{4 - 1} </math>
 
Para h niveles, ahora, la cuestión es determinar la cantidad de niveles en el peor de los casos. La profundidad total del árbol de llamadas recursivas estará dado por la cantidad de veces que se puede dividir el cuadrado. Como el ancho de los cuadraditos está acotado, y en cada paso se divide por dos el ancho del cuadrado original:
 
<math>\frac{a}{2^m}=2</math>
Línea 15:
 
<math>a=2^{m+1}</math>
 
<math>log_2a = m+1</math>
 
Línea 28 ⟶ 29:
 
<math>C = \cfrac{a^2 - 1}{3} </math>
 
El orden de la complejidad del algoritmo queda entonces en función del ancho del cuadrado de entrada, y resulta de <math>O(a^2)</math>.