Page 78 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Si n es igual a 16 se tiene:

T (16) =2T (8) + 2 = 2(2T (4) +2) + 2 = 4T (4) + 4 + 2 = 4(2T (2) +2) +4 +2

T (16) = 8T (2) + 8 + 4 + 2,
donde n = 2 , K = 4 y T (2) = 1; por tanto,
4
T (16) = 2 + 2 – 2 = 3*16 / 2 – 2 = 22.
4
3

Véase que 3n / 2 – 2 es el mejor promedio y peor caso si n es potencia de 2. Contrastado con 2n-2
comparaciones existe un ahorro de 25 %, por lo que es mejor que el secuencial. Pero ¿esto indica
que sea mejor en la práctica? No necesariamente. En términos de almacenamiento es peor, ya que
requiere una pila para guardar a i, j, fmax, fmin. Dados n elementos, se requieren log n +1 niveles de
recursión. Se necesitan guardar cinco valores y el direccionamiento de retorno. Por ende, MaxMin es
más ineficiente porque se maneja una pila y recursión.

72