Analisis de Algoritmos

Análisis de Algoritmos

1. Complejidad de algoritmos
1.1 Introducción
•  Algoritmo: procedimiento computacional
bien definido que toma un valor, o
conjunto de valores, como entrada y
produceun valor, o conjunto de valores,
como salida.

Entrada

Algoritmo

Salida

Propiedades típicas de un algoritmo
(1/2)

Propiedades típicas de un algoritmo
(2/2)

• 
• 
• 
• 

• Finitez: el algoritmo termina; así que, termina
después de que un número finito de instrucciones han
sido ejecutadas.
•  Completez: la salida producida por el algoritmo es
correcta.
•  Generalidad:el algoritmo se aplica a un conjunto de
entradas.

Entrada: el algoritmo recibe una entrada.
Salida: el algoritmo produce una salida.
Precisión: los pasos están indicados de forma precisa.Determinismo: los resultados intermedios de cada
paso de ejecución son únicos y son determinados sólo
por las entradas y los resultados de los pasos
anteriores.

1

Análisis de algoritmos
• Consiste en predecir la cantidad de recursos
(tiempo, memoria, comunicación) que un
algoritmo requerirá para cualquier entrada

Algoritmos
•  Un buen algoritmo es como un cuchillo filoso:
haceexactamente lo que tiene que hacer con
un mínimo esfuerzo.

Ejemplo:
•  Una computadora más rápida (computadora A)
ejecuta 1 billón de instrucciones por segundo y
una computadora más lenta (computadoraB)
sólo 10 millones.
•  Supongamos que un experto programador
implementa el Insertion Sort con 2n2
instrucciones en la computadora A y un
programador novato implementa el Merge-Sort
con 50n lgn instrucciones en la computadora B.

Tiempo de corrida
•  Es el número de “pasos” ejecutados.
•  Este “paso” debe definirse de manera que sea
lo más posible independiente de la máquina.

¿Cuálalgoritmo escoger?
•  Diferentes algoritmos pueden resolver el
mismo problema con dramáticas diferencias
en su eficiencia.

Ejemplo (continuación):
Para ordenar un millón de números el tiempo...