DOI:
https://doi.org/10.14483/22487638.10375Publicado:
2016-05-05Número:
Vol. 19 (2015): Edición EspecialSección:
InvestigaciónTécnica para solución de recurrencias, usada en el análisis de la complejidad de algoritmos recursivos
Technique for recurrences solving, used in recursive algorithm complexity analysis
Palabras clave:
Algoritmos, análisis de algoritmos, cantidad de operaciones, complejidad algorítmica, eficiencia computacional, recurrencias, recursividad. (es).Palabras clave:
Algorithms, algorithmic complexity, Analysis of Algorithms, computational efficiency, operations number, recurrences, recursion (en).Descargas
Resumen (es)
Este artículo presenta un método alternativo, directo y poco común para solucionar recurrencias de primer orden, tanto homogéneas como no homogéneas; aplicable a ecuaciones que representan el comportamiento de algoritmos recursivos. Dicho método se asocia al funcionamiento computacional del algoritmo, facilitando su comprensión y el análisis de la complejidad. El proceso se ilustra con ejemplos de ecuaciones correspondientes a algoritmos muy conocidos y frecuentemente utilizados.
Resumen (en)
This paper shows an alternative, direct and unusual method to solve both first order recurrences homogeneous and inhomogeneous; applicable to equations representing the behavior of recursive algorithms. Such method is associated with the performance of the computational algorithm, by facilitating the understanding and complexity analysis. The process is illustrated by examples of equations for well-known and frequently used algorithms.
Referencias
Aho, A., Hopcroft, J., Ullman, J. (1983). Data structures and algorithms. Massachusetts, U.S.A.: Addison Wesley.
Baase S., Van, A. (1999). Computer Algorithms: Introduction to design and analysis. Massachusetts, U.S.A: Addison Wesley.
Baase, S., Van, A. (2002). Algoritmos computacionales: Introducción al análisis y diseño. México DF, México: Addison Wesley.
Brassard, G., Bratley, P. (1997). Fundamentos de algoritmia. Madrid, España: Prentice Hall.
Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009). Introduction to algorithms. Massachusetts: Massachusetts Institute of Technology.
McConnell, J. (2007). Analysis of Algorithms: an active learning approach. Ontario, Canada: Jones and Bartlett Publisher.
Sedgewick, R. (1995). Algoritmos en C++. Massachusetts, E.U.A.: Addison-Wesley/Díaz de Santos.
Sedgewick, R., Flajolet, P. (2013). An introduction to the analysis of Algorithms. Massachusetts: Pearson Education.
Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
Licencia
Todos los textos incluidos en la Revista Tecnura están protegidos por derechos de autor. Conforme a la ley, está prohibida su reproducción por cualquier medio, mecánico o electrónico, sin permiso escrito del Comité Editorial. Los textos completos de los artículos son de acceso abierto, es decir, se pueden leer, descargar, copiar, distribuir, imprimir, buscar o vincular. Las opiniones expresadas en los artículos publicados son las de los autores y no coinciden necesariamente con las del Comité Editorial ni las de la administración de la Facultad.