análisis de algoritmos

Análisis de Algoritmos
Elizabeth Pérez Cortés
René Mac Kinney Romero
Universidad Autónoma Metropolitana
12 de septiembre de 2005

2

Objetivos
Al nalizar el curso el alumno:
Será capaz de estimar los recursos de cómputo (memoria y tiempo) que
un algoritmo requiere para ejecutarse.
Conocerá y será capaz de utilizar técnicas de diseño adecuadas para
construir soluciones ecientes adiversas clases de problemas.
Reconocerá los problemas para los cuales no se conoce solución algorítmica práctica y podrá aplicar criterios para darles soluciones aproximadas ecientes.

3

4

Prefacio
El concepto de algoritmo es de importancia central en las ciencias de la
computación; matemáticos y cientícos de la computación lo han denido
en forma diferente. La palabra provienedel nombre de un matemático y astrónomo medieval de Uzbekistán, Mohammed ibn-Musa al-Khwarizmi, quien
dio las reglas para efectuar las 4 operaciones aritméticas básicas (suma, resta,
multiplicación y división) en el siglo IX.
El astrónomo medieval se estableció en Bagdad en la Casa del Conocimiento (Bait al-Hikma); escribió dos libros que jugaron un papel importante
en la historia de lasmatemáticas, uno de los cuales concierne al arte indio
de contar. Cuando su obra apareció traducida al latín en Europa, los lectores empezaron a atribuirle no sólo el libro sino, también, un esquema de
numeración que hace uso de numerales indios, esto último se le atribuyó erróneamente. La nueva notación se convirtió en la de al-Khwarizmi, y en forma
descuidada fue nombrada algorismi y, nalmente,algorism o algorithm.
Esta palabra, originalmente derivada del nombre al-Khwarizmi, ahora signica, más ampliamente, cualquier regla particular de proceder u operar (tal
como lo es el método euclidiano para encontrar el máximo común divisor
de dos enteros). A partir de entonces y hasta nuestros días, la palabra, por
todo lo que representa, ha motivado muchos estudios de tipo teórico tantoen matemáticas como en computación.
En la primera parte de este curso se introducen los conceptos básicos
para el análisis de algorítmos; se propone un procedimiento para estimar la
cantidad de recursos que un algoritmo consume cuando se ejecuta en una
computadora. Lo anterior nos permite conocer su valor práctico, es decir,
determinar si existe una solución algorítmica eciente para unproblema en
particular. Enseguida, se da importancia a la velocidad de crecimiento de la
demanda de recursos por un algoritmo, conforme el tamaño del problema que
resuelve se incrementa. El procedimiento presentado nos permite comparar
5

6
y evaluar los costos de algoritmos tanto iterativos como recursivos.
En la segunda parte del curso nos avocamos al estudio de las principales
técnicas dediseño de algoritmos. Para cada una de ellas se caracterizan los
problemas a los que la técnica se puede aplicar, se presenta el método general
y se dan algunos ejemplos.
Finalmente, la tercera parte del curso está enfocada al estudio de la teoría en torno a los problemas cuya solución algorítmica no se conoce o la
conocida requiere tantos recursos que en términos prácticos no resuelve masque problemas triviales. La teoría presentada permite identicar estos problemas así como también encontrar soluciones aproximadas (no óptimas pero
aceptables).

Índice general
I Análisis de algoritmos

11

1. Introducción

13

1.1. Conceptos Básicos . . . . . .
1.1.1. Denición de algoritmo
1.2. Complejidad de algoritmos . .
1.3. Ejercicios . . . . . . . . . . .

.
.
.
.

..
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

2. Comportamiento...
2.1.
2.2.
2.3.
2.4.
2.5.

Dominio asintótico . . . . . . . . . . . . .
Notación de orden . . . . . . . . . . . . . .
Interpretación de los conceptos enunciados
Dominio asintótico con límites . . . . . . .
Ejercicios . . . . . . . . . . . . . . . . . .

3. Análisis de Algoritmos...