Notacion

Análisis de complejidad algorítmica

Roberto Emilio Salas Ruiz Jorge Enrique Rodríguez Rodríguez

Resumen En este artículo se plasma la base del análisis de complejidad algorítmica, para lo que se toma un problema clásico en las ciencias de la computación, como es el ordenamiento de datos. En éste se comparan tres métodos de ordenamiento, a saber, por unión, burbuja e inserción; a cada uno deéstos se le halla el orden de complejidad y se implementan en un lenguaje de programación con el fin de comprobar la teoría frente a la práctica. Finalmente, los autores concluyen los resultados obtenidos. Palabras clave: análisis de complejidad, tiempo de ejecución, algoritmo de ordenamiento, orden de complejidad.

Abstract This paper provides a comprehensive introduction to the algorithmsanalysis. We have one of the most fundamental problems in the computer sciences, the data sorting. We compare three sorting algorithms: merge, bubble and insertion sort. For each algorithm is made an analysis of complexity that is worst-case running time. They were implemented an programming languaje with the objective to contrast theory and practice. Finally, the authors give conclusions aboutresults obtained.
Ingeniero de sistemas, candidato a Magíster en Ingeniería de Sistemas de la Universidad Nacional de Colombia, docente Universidad Distrital Francisco José de Caldas, adscrito a la Facultad Tecnológica. Correo electrónico: rsalas72@hotmail.com. Ingeniero de sistemas, especialista en Diseño y Construcción de Soluciones Telemáticas, especialista en Ingeniería del Software, candidato aMagíster en Ingeniería de Sistemas de la Universidad Nacional de Colombia, docente tiempo completo de la Universidad Distrital Francisco José de Caldas, adscrito a la Facultad Tecnológica. Correo electrónico: jrodri@udistrital.edu.co.

2 Words Keys: analysis of complexity, running time, sorting algorithm, order of complexity.

Introducción Informalmente, un algoritmo es cualquier procedimientocomputacional bien definido que toma algún valor o conjunto de valores como entrada y produce algún valor o conjunto de valores como salida. Así, un algoritmo es una secuencia de pasos computacionales que transforma la entrada en salida. Se puede ver un algoritmo como una herramienta para resolver un problema computacional bien especificado. La declaración del problema especifica, en términosgenerales, las relaciones deseadas entrada/salida; es decir: Entrada: una secuencia de n números Salida: una permutación de la secuencia de entrada tal que a1’ a2’ … an’.

Por ejemplo, dada la secuencia de entrada , un algoritmo de ordenamiento retorna como salida la secuencia . El ordenamiento es una operación fundamental en las ciencias de la computación y, como resultado de esto, un grannúmero de algoritmos de ordenamiento han sido desarrollados. Seleccionar cuál algoritmo es mejor depende, entre otros factores, del número de elementos a ser ordenados, en que grado están los elementos parcialmente ordenados, posibles restricciones en los valores de los elementos y el tipo de dispositivo de almacenamiento a ser utilizado (memoria principal, discos, CD-ROM). Teniendo en cuenta loanterior, es fundamental que los ingenieros del software realicen el análisis de complejidad algorítmica en el diseño de software, ya que, dependiendo del problema a resolver algorítmicamente, éste va a permitir seleccionar el algoritmo más eficiente para tal fin. Del mismo modo, este análisis le permite al ingeniero del software conocer el recurso de máquina (tiempo de ejecución y

3 memoria ocupada)utilizado en la ejecución de un algoritmo, y, de esta forma, minimizar costos de implementación del mismo y optimizar el recurso de máquina. El objetivo principal de este artículo es dar algunos lineamientos para diseñar algoritmos eficientes. Sin embargo, cuando uno se enfrenta con varios algoritmos distintos para resolver el mismo problema, es preciso decidir cuál de ellos es el más adecuado...