Una medida de tamaño apropiado para esta función es el valor de n. Sea T(n) el tiempo de ejecución para fact(n). El tiempo de ejecución para las líneas (1) y (2) es 0(1), y para la línea (3) es 0(1) + 7X*-1). Por tanto, para ciertas constantes c y d.
Esto es, T(n-\) - c + T(n-2)> como se puede ver al sustituir n por n-\ en (1.1). Así pues, es posible reemplazar T(n-\) con c + T(n-2) en la ecuación T(n) - c + T(n-t) Después, se puede usar (1.1) para desarrollar 7\n-2), con lo que se obtieneT(n) - 3c + T(n-3) si« > 3
y así sucesivamente. En general,
T(n) ~ ic + T(n-i) si n > i
Por último, cuando / - /i-l, se obtiene
T(n) - c(n-l) + 7(1) - c(«-l) + d (1.2)
Por eso concluye que T(n) es 0(n). Es importante observar que en este análisis se ha supuesto que la multiplicación de dos enteros es una operación de tiempo 0(1). En la práctica, no obstante, no se puede emplear el programa de la figura 1.14 para calcular n\ cuando los valores de n son grandes, pues el tamaño de los enteros que se calculen excederá del tamaño de palabra de la máquina en cuestión.
El método general para resolver una ecuación de recurrencia, tal como se tipifica en el ejemplo 1.10, consiste en reemplazar en forma repetida términos T(k) del lado derecho de la ecuación por el lado derecho completo, donde k se reemplaza por n, hasta obtener una fórmula en la que Tno aparezca en el lado derecho como en (1.2). A menudo es necesario calcular la suma de una sucesión o, si no es posible encon¬trar la suma exacta, obtener una cota superior cercana para la suma a fin de hallar una cota superior para 7^«).
Bibliografia:
Aho, Alfred V., John E. Hopcroft y Jeffrey D. Ullman. (1998). Diseño y análisis de algoritmos. En Estructuras de datos y algoritmos
No hay comentarios:
Publicar un comentario