Complejidad AA (Algoritmos)

Complejidad Computacional
“Tan pronto como una máquina análitica exista,
será necesario guiar el curso futuro de la ciencia.
Siempre que cualquier resultado sea logrado con
su ayuda, tendrá lugar la pregunta - ¿De qué
forma podemos hacer que la máquina obtenga
los resultados en el menor tiempo posible?”
Charles Babbage, 1864

Objetivos
?

Calcular la complejidad de un algoritmo: en elpeor de los casos y/o en el mejor de los casos, y
determinar sus límites asintóticos.

?

Determinar bajo que circunstancias un algoritmo
es mejor que otro, basándose en la complejidad
temporal.

?

Formular ecuaciones de recurrencia que
describan el comportamiento de un algoritmo
recursivo y resolverlas usando el método de
iteración o el método maestro.

1

ComplejidadComputacional
Temas
Algoritmo
? ¿Qué es un algoritmo?
? Entrada del algoritmo
? Análisis de un algoritmo
? Complejidad

temporal y espacial
? El mejor de los casos, el peor de los casos
y el caso promedio

Complejidad Computacional
Análisis de algoritmos
iterativos y recursivos
? Cálculo

de la complejidad
? Límites asintóticos
? Notación O
? Ecuaciones de recurrencia
? Solución deecuaciones de recurrencia

2

¿Qué es un algoritmo?
?

Es un conjunto claramente especificado de
instrucciones que deben realizarse para resolver
un problema [Baase 91].
? Es un procedimiento bien definido que toma un
conjunto de valores de entrada y produce otro
como salida. Una serie de pasos que transforma
la entrada dada en la salida [Cormen 91].
? Es una especificación noambigua de una
secuencia de pasos que sirven para resolver un
problema [Aho 95].

Entrada del algoritmo
? Los

algoritmos pueden expresarse en un
lenguaje común, pero en computación se
expresan formalmente en un lenguaje de
programación.

? Al

algoritmo se le asocia un número
llamado tamaño del problema, que es una
medida de la cantidad de datos de entrada

3

Análisis de unalgoritmo
? Predecir

la cantidad de recursos que el
algoritmo requerirá para cualquier entrada

? Recursos:

– Almacenamiento principal
– Tráfico generado
– Información almacenamiento secundario
– Simplicidad
– Tiempo de cómputo

Complejidad
Temporal T(n) y Espacial S(n)
T(n): Es el tiempo que requiere un algoritmo
para procesar una entrada de tamaño n.
Sea T(n) la complejidadtemporal de algún
programa, debemos asumir que:
1. El argumento n es un entero no negativo,
2. T(n) es no negativo para todos
los argumentos de n.
Análogamente se define S(n)

4

Análisis de Complejidades
Complejidad en el mejor de los casos
Se define T(n) como el tiempo mínimo de corrida
para todas las entradas de tamaño n.
Complejidad "El peor de los casos":
Se define T(n) como eltiempo máximo de corrida
para todas las entradas de tamaño n.
Complejidad promedio:
Tavg(n) es el tiempo promedio de corrida de un
programa sobre todas las entradas
de tamaño n.

Análisis de algoritmos iterativos
T(n) = ? (NIi * CIi)
? instrucción i.
NI i : es el número de veces que se ejecuta la instrucción i
CI i : es el costo de la instrucción i
void inicializa(int *A, int n) {
1
i=1;2
while (i0 tal que
para todos los enteros n>=n 0, tenemos que:
0 ? c1f(n) ? T(n) ? c2f(n)
3000000
T(n)=2n^2)

2500000

c1f(n)=n^2

2000000

c2f(n)=3n^2
1500000
1000000
500000
0
10

50

100

500

1000

10

Complejidades comunes
Notación
O(1)
O(log n)
O(n)
O(nlogn)

Nombre
constante
logarítmico
líneal
n logn

Notación Nombre
O(n2)
cuadrático
3)
O(ncúbico
O(2n)
exponencial

La regla de la suma: Sea T 1(n) de O(f1(n)) y T2(n)
de O(f2(n)), si f2 no crece tan rápido como f1 (f2 es de
O(f1)) entonces concluimos que:
T1(n) + T2(n) es O(f1(n)).

Ejercicio
Ordenamiento por inserción
1.
2.
3.
4.
5.
6.
7.
8.

for j = 2 to length[A] {
Key = A[j];
i = j-1;
while i > 0 y A[i] > Key {
A[i+1]=A[i];
i=i-1;
}
A[i+1] = Key;
}...