Page 77 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 77
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Por ejemplo:
A(n) 22 13 -5 -8 15 60 17 31 47.
En la figura 2.6 se muestra el árbol recursivo:
Figura 2.6. Árbol recursivo con el algoritmo máximo y mínimo
¿Cuántas comparaciones se requieren?
Cuando n es potencia de 2, n = 2 . Por lo tanto,
k
T(n) = 2T(n/2) +2 = 2(2T(n/4)+2)+2 = 4T(n/4) + 4 +2 = 4(2T(n/8)+2) + 4 + 2 T(n) = 8T(n/8)+8 + 4 + 2
= 8(2T(n/16)+2) + 8 + 4 + 2 = 16T(n/16)+16+8+4+2 . . .
T(n) = 2 k – 1 T (2) + ∑2 = 2 k – 1 + 2 -2 = 3n/2 – 2,
k
i
donde 2 k – 1 = n / 2 y la sumatoria corre de la siguiente forma: 1 ≤ i ≤ k-1.
71
