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.