Análisis de Algoritmos: Complejidad

Análisis de Algoritmos: Complejidad

Contenido

• Introducción

• Tiempo de Ejecución

• Asíntotas

• Reglas Practicas

• Problemas P, NP y NP-completos

1. Introducción

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.

Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.

2. Tiempo de Ejecución

Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como

S1; for (int i= 0; i < N; i++) S2;

requiere

T(N)= t1 + t2*N

siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".

Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que mas que un valor T(N) debamos hablar de 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 algun "caso promedio" o más frecuente.

Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes "Ti" que dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta. Dado que es fácil cambiar de compilador y que la potencia de los ordenadores crece a un ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los algoritmos con algun nivel de independencia de estos factores; es decir, buscaremos estimaciones generales ampliamente válidas.

3. Asíntotas

Por una parte necesitamos analizar la potencia de los algoritmos independientemente de la potencia de la máquina que los ejecute e incluso de la habilidad del programador que los codifique. Por otra, este análisis nos interesa especialmente cuando el algoritmo se aplica a problema grandes. Casi siempre los problemas pequeños se pueden resolver de cualquier forma, apareciendo las limitaciones al atacar problemas grandes. No debe olvidarse que cualquier técnica de ingeniería, si funciona, acaba aplicándose al problema más grande que sea posible: las tecnologias de éxito, antes o después, acaban llevándose al límite de sus posibilidades.

Las consideraciones anteriores nos llevan a estudiar el comportamiento de un algoritmo cuando se fuerza el tamaño del problema al que se aplica. Matemáticamente hablando, cuando N tiende a infinito. Es decir, su comportamiento asintótico.

Sean "g(n)" diferentes funciones que determinan el uso de recursos. Habra funciones "g" de todos los colores. Lo que vamos a intentar es identificar "familias" de funciones, usando como criterio de agrupación su comportamiento asintótico.

A un conjunto de funciones que comparten un mismo comportamiento asintótico le denominaremos un orden de complejidad'. Habitualmente estos conjuntos se denominan O, existiendo una infinidad de ellos.

Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la clase, hablándose del conjunto de funciones "g" que son del orden de "f(n)", denotándose como

g IN 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".

La definición matemática de estos conjuntos debe ser muy cuidadosa para involucrar ambos aspectos: identificación de una familia y posible utilización como cota superior de otras funciones menos malas:

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)) está 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

...