DOI:
https://doi.org/10.14483/22487638.10375Publicado:
05-05-2016Nú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
Esta licencia permite a otros remezclar, adaptar y desarrollar su trabajo incluso con fines comerciales, siempre que le den crédito y concedan licencias para sus nuevas creaciones bajo los mismos términos. Esta licencia a menudo se compara con las licencias de software libre y de código abierto “copyleft”. Todos los trabajos nuevos basados en el tuyo tendrán la misma licencia, por lo que cualquier derivado también permitirá el uso comercial. Esta es la licencia utilizada por Wikipedia y se recomienda para materiales que se beneficiarían al incorporar contenido de Wikipedia y proyectos con licencias similares.
