09. Introducción a la complejidad
Introducción
En este módulo se introduce el concepto de complejidad y de análisis de algoritmos.
Cuando se plantea la necesidad de resolver un problema mediante el desarrollo de un algoritmo, en la gran mayoría de los casos existen varias soluciones posibles. En consecuencia, es necesario disponer de criterios para escoger de entre las alternativas disponibles. Este módulo analiza algunos de los criterios más utilizados en este contexto.
Eficiencia de los algoritmos
De la eficiencia de un algoritmo no tiene relación con que este sea fácil de escribir, modificar o entender. En un algoritmo que se ejecuta con poca frecuencia el coste relativo de desarrollo tiene mayor peso, mientras que en un algoritmo que se ejecuta con mucha frecuencia el coste relativo de desarrollo tiene menos importancia.
La eficiencia de un algoritmo se puede cuantificar según la cantidad de recursos computacionales que se utilice en su ejecución. A mayor tiempo de ejecución se puede decir que utilizará más recursos, por lo tanto el tiempo de ejecución podría ser una medida de eficiencia. Si lo que miramos es la cantidad de memoria utilizada por el algoritmo, se podría decir que es más eficiente el que consume menos memoria.
Una estrategia para decidir qué algoritmo es el más eficiente para resolver un determinado problema dado un conjunto de algoritmos posibles, sería implementarlos todos y ejecutarlos.
Esta estrategia tiene varios inconvenientes:
- No es posible a veces implementar todos los algoritmos posibles ya que representa un esfuerzo considerable.
- El comportamiento de un algoritmo en una máquina concreta no aporta suficiente información sobre como se comportará el mismo algoritmo en otra máquina diferente.
Por lo tanto el objetivo consiste en estudiar las propiedades del algoritmo e implementar unicamente la versión que se considera mejor.
El tiempo de ejecución de un algoritmo depende habitualmente de:
- Los datos de entrada.
- La calidad del código generada por el compilador.
- La máquina donde se ejecuta el programa.
- La complejidad de tiempo del algoritmo base del programa.
La complejidad de un algoritmo se define en función de los datos de entrada. Por ejemplo, supongamos un algoritmo que realiza una búsqueda de un elemento dado en una una secuencia de números. Si tenemos la siguiente secuencia de entrada: {8, 3, 5, 7} , decimos que el tamaño de la entrada es n=4, siendo n el número de elementos de la secuencia.
En adelante vamos a denotar como T( n ) la función de tiempo de ejecución de un algoritmo cuya entrada tiene tamaño n. T( n ) se expresa sin unidades y representa la cantidad de operaciones elementales que realiza el algoritmo necesarias para obtener la solución. Se consideran operaciones elementales las asignaciones, comparaciones, operaciones aritméticas...
Ejemplo: tiempo de ejecución de una función iterativa
La siguiente función iterativa que calcula la suma de los elementos de un vector:
[Ejemplo 09_01]
function sumVectorIterative(v: vector [N] of integer, n: integer): integer
var
i, result: integer;
end var
i := 1;
result := 0;
while i ≤ n do
result := result + v[i];
i := i + 1;
end while
return result;
end function
int sumVectorIterative(int v[N], int n) {
int i, result;
i = 0;
result = 0;
while (i < n) {
result = result + v[i];
i = i + 1;
}
return result;
}
En este algoritmo se realizan primero dos inicializaciones y luego un recorrido por todo el vector de n iteraciones, y en cada iteración se realiza una comparación (la de la condición de fin del bucle), dos asignaciones, dos operaciones de suma y un acceso a una posición del vector. Notar que existe una evaluación extra de la condición de fin del bucle cuando ésta evalúa a Falso y el bucle acaba. Dado que las comparaciones, sumas, asignaciones y accesos al vector se consideran operaciones elementales, tenemos que el algoritmo realiza 6n operaciones elementales (operaciones del bucle) y otras 3 operaciones (2 al inicio y 1 extra para salir del bucle). Por lo que la función de tiempo de ejecución del algoritmo decimos que es T( n )= 3 + 6n.
Hay casos en los que el análisis de la función del tiempo no es tan simple y el número de iteraciones del algoritmo depende del tamaño de la entrada concreta.
Ejemplo: tiempo de ejecución de un algoritmo
El siguiente ejemplo estudia el tiempo de ejecución de un algoritmo que busca un elemento en un vector:
[Ejemplo 09_02]
function findElemVector(v: vector [N] of integer, n: integer; key: integer): boolean
var
i: integer;
found: boolean;
end var
i := 1;
found := false;
while found = false and i ≤ n do
if v[i] = key then
found := true;
end if
i := i + 1;
end while
return found;
end function
boolean findElemVector(int v[N], int n, int key) {
int i;
boolean found;
i = 0;
found = FALSE;
while (found == FALSE && i <= n) {
if (v[i] == key) {
found = TRUE;
}
i=i+1;
}
return found;
}
En este algoritmo se realizan primero dos asignaciones y luego un bucle. Por cada iteración de bucle se realizan tres comparaciones, una operación and, una suma, una asignación y un acceso al vector, todas ellas operaciones elementales. La asignación dentro de la sentencia condicional se realizará sólo una vez. La evaluación de la condición del bucle se realiza una vez más que el número total de iteraciones (la última vez que se evalúa y resulta falso el resultado).
Dado que el vector no está ordenado se debe comprobar todos los elementos del vector para ver si el elemento se encuentra o no. En caso de que el elemento a buscar no esté en el vector, el bucle realizará n iteraciones. En el caso en el que el elemento esté en la posición i = k, entonces el bucle realizará k iteraciones.
En este ejemplo tiene sentido hablar de tiempo de ejecución promedio y haría referencia a la media de todos los tiempos de ejecución posibles del algoritmo. Para calcular este tiempo de ejecución promedio sin embargo, sería necesario tener información sobre la entrada promedio o la probabilidad de que cada posible entrada sea utilizada. Esta información no siempre está disponible, y por otro lado, si lo estuviera, el cálculo puede ser matemáticamente muy complejo. En consecuencia, cuando se hable de tiempo de ejecución T( n ) siempre se hará referencia al tiempo de ejecución del peor caso.
En este ejemplo el peor caso es cuando el elemento no está en el vector. Así entonces, el número de iteraciones será n, igual al tamaño del vector.
Teniendo en cuenta todo lo anterior, podemos decir que el tiempo de ejecución del peor caso es T( n ) = 5 + 7n
De forma análoga se puede hablar del mejor caso, que sería cuando el elemento a buscar está en la primera posición del vector (k = 1). En este caso el tiempo de ejecución sería constante. Esta medida no proporciona una idea realista del crecimiento del tiempo de ejecución del algoritmo al aumentar el tamaño de la entrada, por lo tanto no la utilizaremos.
Estas medidas de tiempo de ejecución sirven para realizar comparaciones entre diferentes implementaciones de un algoritmo pero no sirven para medir el tiempo de ejecución real dado que este depende como se ha comentado antes de otros factores. Por lo tanto, el objetivo es comparar tiempos de ejecución y como varía al aumentar el tamaño de la entrada. Por ejemplo, un algoritmo A con T( n ) = 2n si lo comparamos con otro con T( n ) = 2n2 diremos que el primero es más eficiente que el segundo puesto que a medida que aumenta la entrada, el valor de T aumentará más lentamente con el primero que con el segundo.
En resumen no se puede decir que un algoritmo es el más eficiente de todos, sino que solo se puede hablar de que un algoritmo es más eficiente que otro.
En la tabla 1 se muestra una lista de funciones de tiempo de ejecución ordenadas según su velocidad de crecimiento al aumentar el tamaño de la entrada. Se comienza por las que muestran un crecimiento menor (más eficiente) hasta la última que tiene un crecimiento más rápido (menos eficiente). Un algoritmo con función de tiempo constante T( n ) = k se considera eficiente, ya que no importa el tamaño de la entrada, el algoritmo no crece su tiempo de ejecución.
Tabla 1. Funciones habituales para el estudio de la eficiencia de algoritmos
| Velocidad de crecimiento | Nombre |
|---|---|
| k | constante |
| log ( n ) | logarítmico |
| n | lineal |
| n log ( n ) | casi-lineal |
| n2 | cuadrática |
| nk | polinómica |
| 2n | exponencial |
Notación asintótica
Decir que la función tiempo de ejecución de un algoritmo, es T( n ) igual a una función f( n ), siendo ésta por ejemplo f( n ) = n2 o f( n ) = log ( n ), equivale a decir que T( n ) es proporcional a la función f( n ).
El comportamiento asintótico de un problema se refiere a el comportamiento de un algoritmo cuando el tamaño de la entrada crece.
A un conjunto de funciones que comparten el mismo comportamiento asintótico le denominamos orden de complejidad. Habitualmente estos conjuntos se denominan O. Cada uno de estos conjuntos se suele identificar mediante un miembro f( n ) que se utiliza como representante del conjunto o clase. Por lo que diremos que el conjunto de funciones "g" son del orden de f( n ), es decir que g Є O(f( n )).
En muchas situaciones no es necesario conocer el comportamiento exacto del algoritmo, sino que es suficiente con conocer una cota superior, es decir una función que se comporte todavía "peor". Así pues diremos que O(f( n )) representa al conjunto de todas las funciones g( n ) que crecen, como mucho tan rapidamente como f( n ), donde n es un número natural. A este conjunto de funciones se las puede definir como se muestra en la ecuación 1:
O(f( n )) := {g( n ) | ∃ c, n0 > 0, ∀n ≥ n0 : g( n ) ≤ c.f( n ) } (1)
La ecuación 1 dice que una función g( n ) está en el conjunto O( f ) si es posible encontrar un valor n0 a partir del cual f( n ) sea siempre mayor o igual que g( n ).
En definitiva lo que nos indica esta notación es que si tenemos un algoritmo cuyo tiempo de ejecución es f( n ), podemos encontrar otra función de n, g( n ) y un tamaño de problema n0 de tal forma que f( n ) acota superiormente al tiempo de ejecución para todos los problemas de tamaño superior a n0.
Diremos que f( x ) domina asintóticamente a g( x ), si f( x ) domina a g( x ) para valores muy grandes de x.
Por ejemplo, si g( n ) = n2 + 5n + 100 y f( n ) = n2 entonces f( n ) domina a g( n ) si existe una constante de proporcionalidad c (por ejemplo c = 2) que permite que a partir de cierto n (n = 13), f( n ) es siempre mayor que g( n ).
Esta notación facilitará las comparaciones de eficiencia entre algoritmos diferentes. En la figura 1 se muestra algunos ejemplos de velocidad de crecimiento de las funciones más comunes en el análisis de algoritmos al variar n (el tamaño de la entrada).
Figura 1. Ejemplo de la velocidad de crecimiento de las funciones más comunes en el análisis de algoritmos
Ejemplo: orden de complejidad de un algoritmo
[Ejemplo 09_03]
for i := 1 to n
for j := 1 to n
result := i+j;
end for
end for
La sentencia (3) tiene orden constante, es decir O( 1 ). Dado que la complejidad del bucle es el producto del número de ejecuciones por la complejidad de las sentencias ejecutadas, tenemos que el código que va desde la sentencia (2) hasta la sentencia (4) tienen complejidad O( n ). Y finalmente el código que va desde la sentencia (1) hasta la sentencia (5) ejecuta el código de la sentencia (3), n.n veces, por lo tanto el orden de complejidad de este código es O(n2).
Resumen
En este módulo hemos introducido el concepto de complejidad.
Para resolver un problema pueden existir varios algoritmos. Por tanto es necesario definir un criterio para decidir cuál es el más adecuado.
Se introduce el concepto de eficiencia de un algoritmo relacionado con el tiempo de ejecución del mismo. El tiempo de ejecución depende del tamaño de la entrada.
Se definen así el mejor caso, el peor caso y el caso medio a la hora de analizar los tiempos de un algoritmo.
Para medir la eficiencia se introduce la notación asintótica que nos facilitará la comparación entre algoritmos diferentes.