Análisis y Diseño de Algoritmos : Conceptos básicos

Análisis y Diseño de Algoritmos
5 de octubre de 2010

Índice
1. Introducción
1.1. Conceptos básicos y ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Entrando en materia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2
3

2. Notación asintótica

6

3. Referencias

6

Análisis y Diseño de Algoritmos
1.Introducción

¿Por qué estudiar Análisis y Diseño de Algoritmos?
El equipo de cómputo se vuelve más rápido cada vez. ¿No parece una pérdida de tiempo diseñar algoritmos más e…cientes en vez de esperar a la siguiente generación de computadoras? Pues no lo es. Veamos.
Supongamos que para resolver un problema tienes un algoritmo exponencial y una computadora que puede
correr este algoritmo eninstancias de tamaño n en 10 4 2n segundos. Tu programa puede resolver instancias de tamaño 10 en 10 4 210 segundos o 0.1024 segundos. Para instancias de tamaño 20 en casi dos
minutos. Para resolver instancias de tamaño 30 le tomara muchísimo más tiempo, un día entero no sería
su…ciente. Ahora supongamos que dejas funcionando tu algoritmos en tu computadora por un año entero sin
interrupciones ysin errores (un escenario no muy realista), solo podrás resolver instancias de tamaño 38.
Ahora supongamos que tienes los recursos necesarios para conseguir una computadora 100 veces más
rápida que la anterior, intuitivamente podrás pensar que con esa computadora serás capaz de resolver instancias de tamaño 38 100=3800. Eso no es verdad en lo absoluto. Ahora eres capaz de resolver instancias
detamaño n en 10 6 2n segundos con el mismo algoritmo, por lo que resolverás instancias de tamaño 45
en un año entero. Comprar una computadora más potente y costosa no es la solución.
Supongamos que en vez de comprar esa costosísima computadora, investigas en el diseño e…ciente de
algoritmos y encuentras un algoritmo cúbico para resolver tu problema. Con este nuevo algoritmo puedes
resolverinstancias de tamaño n en 10 4 n3 segundos. Así que, con la computadora original, te toma 10
segundos resolver una instancia de tamaño 10, y para una instancia de tamaño 20 te toma entre uno y dos
minutos (parece que no haya mejoría). Pero para instancias de tamaño 30 lo puedes resolver en 4 minutos y
medio, y en un día entero puedes resolver tamaños más grandes que 200; con un año de computaciónpuedes
resolver instancias de por lo menos 1500.
Con esto vemos la verdadera importancia que tiene el estudio de los algoritmos. El resultado de un
algoritmo puede ser poco fructífero aun en la computadora más rápida del mundo. Aun así, si requerimos
resolver instancias de tamaño menor a 20 podemos utilizar el primer algoritmo, y usar el segundo si nuestro
tamaño de instancia es superior.Pero, ¿qué es Diseño y análisis de algoritmos?
De manera general, podemos ejempli…carlo con los siguientes puntos:
Plantea y resuelve problemas de manera algorítmica.
1

Determina lo que puede computarse e…cientemente.
De…ne y caracteriza nuevos objetos de cómputo (nuevas estructuras de datos, paradigmas de programación, técnicas de programación,...)

1.1.

Conceptos básicos y ejemplosEn el diseño y análisis de algoritmos se sigue un proceso que sigue, a grandes razgos, los siguientes pasos:
1. Planteamiento del problema.
2. Medición del tamaño (longitud) del problema.
3. Propuestas de algortimos. (Diseño de algoritmos).
4. Análisis de las propuestas de algoritmos (Análisis de algoritmos).
5. Comparación de los resultados que arroja el análisis de algoritmos.
Elplanteamiento del problema, al igual que el resto de los pasos, es fundamental para continuar con el
proceso, siendo que este paso sienta la base en lo que se basará el resto. Luego, sigue la medición del problema,
este puede variar entre instancias del problema, pero se puede generalizar. A continuación se proponen los
algoritmos que pueden resolver el problema. El análisis de dichos algoritmos arroja...