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 h 141 4 h

n3 1 h 126 8 h

2n 1 h 101 1030 h

Los algoritmos de complejidad O(n) y O(n log n) son los que muestran un comportamiento más "natural": prácticamente a doble de tiempo, doble de datos procesables.

Los algoritmos de complejidad logarítmica son un descubrimiento fenomenal, pues en el doble de tiempo permiten atacar problemas notablemente mayores, y para resolver un problema el doble de grande sólo hace falta un poco más de tiempo (ni mucho menos el doble).

Los algoritmos de tipo polinómico no son una maravilla, y se enfrentan con dificultad a problemas de tamaño creciente. La práctica viene a decirnos que son el límite de lo "tratable".

Sobre la tratabilidad de los algoritmos de complejidad polinómica habria mucho que hablar, y a veces semejante calificativo es puro eufemismo. Mientras complejidades del orden O(n2) y O(n3) suelen ser efectivamente abordables, prácticamente nadie acepta algoritmos de orden O(n100), por muy polinómicos que sean. La frontera es imprecisa.

Cualquier algoritmo por encima de una complejidad polinómica se dice "intratable" y sólo será aplicable a problemas ridiculamente pequeños.

A la vista de lo anterior se comprende que los programadores busquen algoritmos de complejidad lineal. Es un golpe de suerte encontrar algo de complejidad logarítmica. Si se encuentran soluciones polinomiales, se puede vivir con ellas; pero ante soluciones de complejidad exponencial, más vale seguir buscando.

No obstante lo anterior ...

• ... si un programa se va a ejecutar muy pocas veces, los costes de codificación y depuración son los que más importan, relegando la complejidad a un papel secundario.

• ... si a un programa se le prevé larga vida, hay que pensar que le tocará mantenerlo a otra persona y, por tanto,

...