Page 28 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 28
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
La relación de recurrencia es esta:
T(n) = 2 T(n/2) + O (n)
T (1) = O (1)
Y el problema es cómo deducir, a partir de esa definición, la complejidad del algoritmo completo.
Para resolverlo, se van aplicando pasos sucesivos de recursión:
T(n) = 2 T(n/2) + n
T(n) = 2 (2 T(n/4) + n/2) + n = 4 T(n/4) + 2n
T(n) = 8 T(n/8) + 3n
hasta que se vea un patrón
T(n) = 2k T(n/2k) + k n
Esta fórmula es válida siempre, en particular cuando n/2 = 1 y podemos escribir
k
T(n) = 2 T (1) + k n
k
y como sabemos la condición de parada de la recursión
T(n) = 2 + k n
k
El valor de k que termina la recursión es:
n/2 = 1 => k = log2(n),
k
sustituyendo
T(n) = 2 log (n) + log2(n) n
2
T(n) = n + n log(n) => O (n log(n))
El método descrito permite resolver numerosas relaciones de recurrencia. Algunas son muy habitua-
les (tabla 1.5).
22
