Analisis De Algoritmos

Análisis de Algoritmos: Complejidad

José A. Mañas

Noviembre, 1997

1. Introducción

2. Tiempo de Ejecución

3. Asintotas

4. Reglas Practicas

5. Problemas P, NP y NP-completos

6. Conclusiones

7. Bibliografia

1. Introducción

2. Tiempo de Ejecución

T(N) = el número de instrucciones a ejecutar en un algoritmo

Sentencias cíclicas {for, while, do while, etc}

for (i= 0; i < N; i++){

S2= número de instrucciones en el ciclo

}

Requiere T(N)= s2*N

Sentencias cíclicas anidadas

for (i= 0; i < N; i++){

for (j= 0; j < M; j++){

S2= número de instrucciones en el ciclo

}

}

Requiere T(N)= N*M*S2

En general

Con k ciclos anidados

Donde el número de instrucciones del ciclo k es Nk se tiene que:

Requiere T(N)= Ni*N2*N3*…*Nk*S2

Sentencias if

If ( cond) then {

m sentencias

}

else{

k sentencias

}

En una sentencia condicional no siempre se ejecutan las mismas instrucciones esto depende de los datos concretos que se le presenten. T(N) tiene un rango de valores

Tmin(N) <= T(N) <= Tmax(N)

los extremos son habitualmente conocidos como "caso peor" y "caso mejor". Entre ambos se hallara algún "caso promedio" o más frecuente.

3. Asíntotas

T(n) puede tener diferentes tipos de crecimiento. Estas funciones se clasifican de acuerdo a su comportamiento asintótico. Para identificar a cada clase se utiliza un representante de la clase. Entonces un algoritmo g(n) se dice que pertenece a la clase C, de la cual f(n) es el representante, escribiendo

g(n)=O(f(n))

Con frecuencia nos encontraremos con que no es necesario conocer el comportamiento exacto, sino que basta conocer una cota superior, es decir, alguna función que se comporte "aún peor".

Dícese que el conjunto O(f(n)) es el de las funciones de orden de f(n), que se define como

O(f(n))= {g: INTEGER -> REAL+ tales que

existen las constantes k y N0 tales que

para todo N > N0, g(N) <= k*f(N) }

en palabras, O(f(n)) esta formado por aquellas funciones g(n) que crecen a un ritmo menor o igual que el de f(n).

De las funciones "g" que forman este conjunto O(f(n)) se dice que "están dominadas asintóticamente" por "f", en el sentido de que para N suficientemente grande, y salvo una constante multiplicativa "k", f(n) es una cota superior de g(n).

3.1. Órdenes de Complejidad

Se dice que O(f(n)) define un "orden de complejidad". Escogeremos como representante de este orden a la función f(n) más sencilla del mismo. Así tendremos

O(1) orden constante

O(log n) orden logarítmico

O(n) orden lineal

O(n log n)

O(n2) orden cuadrático

O(na) orden polinomial (a > 2)

O(an) orden exponencial (a > 2)

O(n!) orden factorial

Es más, se puede identificar una jerarquía de órdenes de complejidad que coincide con el orden de la tabla anterior; jerarquía en el sentido de que cada orden de complejidad superior tiene a los inferiores como subconjuntos. Si un algoritmo A se puede demostrar de un cierto orden O1, es cierto que tambien pertenece a todos los órdenes superiores (la relación de orden çota superior de' es transitiva); pero en la práctica lo útil es encontrar la "menor cota superior", es decir el menor orden de complejidad que lo cubra.

3.1.1. Impacto Práctico

Para captar la importancia relativa de los órdenes de complejidad conviene echar algunas cuentas.

Sea un problema que sabemos resolver con algoritmos de diferentes complejidades. Para compararlos entre si, supongamos que todos ellos requieren 1 hora de ordenador para resolver un problema de tamaño N=100.

¿Qué ocurre si disponemos del doble de tiempo? Notese que esto es lo mismo que disponer del mismo tiempo en un odenador el doble de potente, y que el ritmo actual de progreso del hardware es exactamente ese:

"duplicación anual del número de instrucciones por segundo".

¿Qué ocurre si queremos resolver un problema de tamaño 2n?

O(f(n)) N=100 t=2h N=200

log n 1 h 10000 1.15 h

n 1 h 200 2 h

n log n 1 h 199 2.30 h

n2 1

...