Grafos y algoritmos
Complejidad de un algoritmo. NP-completitud I Algoritmos de ordenación I Algoritmos de búsqueda I Algoritmo voraz

2.1. Complejidad de un algoritmo

En el desarrollo de un programa computacional resulta necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.

Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en ejecutarse. Ambos representan los costes que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado de entre varios que solucionan un mismo problema. En esta sección nos referiremos exclusivamente a la eficiencia temporal.

El análisis de la eficiencia temporal de los algoritmos consta de dos fases: análisis a priori y análisis a posteriori.

El análisis a posteriori ofrece una medida real, consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto.

El análisis a priori proporciona una medida teórica, que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados.  Esta medida ofrece estimaciones del comportamiento de los algoritmos de forma independiente del ordenador en donde serán implementados y sin necesidad de ejecutarlos. La unidad de tiempo a la que debe hacer referencia esta medida de eficiencia temporal no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no existe un ordenador estándar al que puedan hacer referencia todas las medidas. Esta medida de eficiencia temporal se define como una función del tamaño o talla de la entrada.

Definición 2.1.1. Se denomina tamaño de la entrada el número de componentes sobre los que se va a ejecutar el algoritmo.

Por ejemplo, la dimensión del vector a ordenar o el tamaño de las matrices a multiplicar. En el caso de algoritmos que resuelvan determinado problema sobre grafos el tamaño de la entrada podría ser el número de vértices o el número de aristas.

Denotaremos por T(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n, donde T(n) indica el número de instrucciones ejecutadas por un ordenador idealizado.

Principio de Invarianza. Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2(n) segundos respectivamente, existe una constante real c > 0 y un número natural n0 tales que para todo  se verifica que .

Es decir, el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado, ya sea del mismo código ejecutado por dos máquinas de distinta velocidad, como de dos códigos diferentes que implementen el mismo método, no va a diferir más que en una constante multiplicativa.

Definición 2.1.2. Se dice que un algoritmo tarda un tiempo del orden de T(n) si existen una constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo n tamaño de la entrada.

El comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas pues para muchos programas el tiempo de ejecución es en realidad una función de la entrada específica, y no sólo del tamaño de ésta. Así suelen estudiarse tres casos para un mismo algoritmo: caso peor, caso mejor y caso medio.

El caso mejor corresponde a la traza (secuencia de sentencias) del algoritmo que realiza menos instrucciones. Análogamente, el caso peor corresponde a la traza del algoritmo que realiza más instrucciones, lo cual nos asegura que al menos el algoritmo se desempeñará de esa forma . Respecto al caso medio, corresponde a la traza del algoritmo que realiza un número de instrucciones igual a la esperanza matemática de la variable aleatoria definida por todas las posibles trazas del algoritmo para un tamaño de la entrada dado, con las probabilidades de que éstas ocurran para esa entrada. Esta es la medida más difícil de calcular pues debemos saber cómo están distribuidos los datos. Por otra parte, sino conocemos la distribución de las entradas, entonces la mejor opción es analizar el caso peor.

A la hora de medir el tiempo, siempre lo haremos en función del número de operaciones elementales que realiza el algoritmo dado, entendiendo por operaciones elementales aquellas que el ordenador realiza en tiempo acotado por una constante. Así, consideraremos operaciones elementales las operaciones aritméticas básicas, asignaciones a variables de tipo predefinido por el compilador, los saltos (llamadas a funciones y procedimientos, retorno desde ellos, etc.), las comparaciones lógicas y el acceso a estructuras indexadas básicas, como son los vectores y matrices. Cada una de ellas contabilizará como 1 operación elemental. Resumiendo, el tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales que realiza el algoritmo para un tamaño de entrada dado.

Analicemos el siguiente algoritmo para determinar si un grafo es o no bipartido.

PROCEDURE Bipartido(VAR n : INTEGER, a: MATRIX) INTEGER

VAR clase :vector, i : INTEGER, j :INTEGER;

BEGIN

(1)           clase[1]=0;

(2)           IF a[1][2]==0 THEN clase[2]=0;

ELSE clase[2]=1;

(3)           FOR i=3 TO n DO

(4)                          IF a[1][i]==0 THEN clase[i]=0;

ELSE clase[i]=1;

(5)                          FOR j=2 TO i-1 DO

(6)                                          IF clase[i]==clase[j]  &&  a[i][j]=1 THEN 

RETURN  0;

END

END

(7)           FOR i=1 TO n DO

(8)                          PRINT clase[i];

END

RETURN 1;

END

En este algoritmo n es el número de vértices del grafo, a es la matriz de adyacencia del grafo y clase es un arreglo con elementos iguales a 0 ó 1 en dependencia de la clase que se le asigna a cada vértice. El procedimiento devuelve 1 si el grafo es bipartido o 0 en caso contrario. Si el grafo es bipartido se imprime el arreglo clase.

El caso mejor se produce cuando el grafo no es bipartido y los vértices 1, 2 y 3 están conectados entre sí, pues entonces el algoritmo realiza sólo la operación del paso (1), las dos operaciones del paso (2),  las dos operaciones del paso (4) y las tres operaciones del paso (6), es decir que T(n)=8.

El caso peor se produce o bien cuando el grafo es bipartido o bien cuando el grafo no es bipartido pero la contradicción aparece al asignar la clase al último vértice. Calculemos T(n) para el caso cuando el grafo es bipartido.

(1)   una operación

(2)   dos operaciones

(3)   se realiza n-2 veces

(4)   dos operaciones

(5)   se realiza i-2 veces para i desde 3 hasta n

(6)   dos operaciones

(7)   se realiza n veces

(8)   una operación

Definición 2.1.3 Sea  Se define el conjunto de funciones de orden O(f) como el conjunto de todas las funciones para las cuales existen  y tales que . Diremos que una función es de orden O( f) si .

Definición 2.1.4. Dado un algoritmo diremos que su orden de complejidad es O(f) si su tiempo de ejecución para el peor caso es de orden O( f), es decir, T(n) es de orden O(f).

Intuitivamente, indica que t está acotada superiormente por algún múltiplo de f. Normalmente estaremos interesados en la menor función f tal que t pertenezca a O(f). Así tendremos:

O(1)                orden constante

O(log n)         orden logarítmico

O(n)                orden lineal

O(n2 )             orden cuadrático

O(na)              orden polinomial (a > 2)

O(an)              orden exponencial (a > 1)

O(n!)               orden factorial

 

En la siguiente tabla se comparan los tiempos para los diferentes ordenes de complejidad.

n

log n

n2

2n

n!

2

1

4

4

2

8

3

64

256

40320

32

5

1024

4,3 x 109

2,6 x 1035

100

6

104

1,2 x 1027

9,3 x 10177

Como puede observarse los algoritmos cuya complejidad es descrita por una función polinomial pueden ser ejecutados para entradas grandes en una cantidad de tiempo razonable, mientras que los algoritmos exponenciales son de poca utilidad excepto para entradas pequeñas.

DESCARGAR ESTE ARCHIVO EN PDF