Page 32 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 32
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
El análisis del método potencia es delicado, pues si el exponente es par, el problema tiene una evo-
lución logarítmica; en cambio, si es impar, su evolución es lineal. No obstante, como si j es impar,
entonces j-1 es par; el caso peor es que en la mitad de los casos tengamos j”impar y en la otra mitad
par. El caso mejor, por contra, es que siempre sea j par.
Un ejemplo de caso peor sería x ^ 31, que implica la siguiente serie para j:
31 30 15 14 7 6 3 2 1,
cuyo número de términos podemos acotar superiormente por
2 * Valor_Superior (log (j)),
2
donde Valor_Superior(x) es el entero inmediatamente superior (este cálculo responde al razonamien-
to de que en el caso mejor visitaremos Valor_Superior (log (j)) valores pares de j; y en el caso peor
2
podemos encontrarnos con otros tantos números impares entremezclados).
Por tanto, la complejidad de potencia es de orden O (log n). Otra forma de calcularlo es replantear la
función recursiva, como se muestra en el algoritmo 1.6.
Algoritmo 1.6. Evaluación del polinomio P(x) en forma recursiva
26
