Introducción a la Complejidad Computacional
| 1.1 | Análisis de Algoritmos |
| 1.2 | Concepto de Complejidad |
| 1.3 | Aritmética de Notación O |
| 1.4 | Complejidad en Espacio |
| 1.5 | Selección de un Algoritmo |
Dado que el objeto fundamental de este tema son los algoritmos vamos a empezar por establecer una definición de lo que es un algoritmo: Secuencia finita de instrucciones donde cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de recursos computacionales en un tiempo finito.
El análisis de algoritmos es una herramienta para hacer la evaluación del diseño de un algoritmo, permite establecer la calidad de un programa y compararlo con otros que puedan resolver el mismo problema, sin necesidad de desarrollarlos. El analisis de algoritmos estudia, desde un punto de vista teórico, los recursos computacionales que requiere la ejecución de un programa, es decir su eficiencia (tiempo de CPU, uso de memoria, ancho de banda, ...). Además de la eficiencia en el desarrollo de sofware existen otros factores igualmente relevantes: funcionalidad, corrección, robustez, usabilidad, modularidad, mantenibilidad, fiabilidad, simplicidad y aún el propio costo de programación.
El análisis de algoritmos se basa en:
Determinar la eficiencia de un algoritmo nos permite establecer lo que es factible en la implementación de una solución de lo que es imposible.
- Tipos de Análisis:
Los criterios para evaluar programas son diversos: eficiencia, portabilidad, eficacia, robustez, etc. El análisis de complejidad está relacionado con la eficiencia del programa. La eficiencia mide el uso de los recursos del computador por un algoritmo. Por su parte, el análisis de complejidad mide el tiempo de cálculo para ejecutar las operaciones (complejidad en tiempo) y el espacio de memoria para contener y manipular el programa más los datos (complejidad en espacio). Así, el objetivo del análisis de complejidad es cuantificar las medidas físicas: tiempo de ejecución y espacio de memoria y comparar distintos algoritmos que resuelven un mismo problema.
El tiempo de ejecución de un programa depende de factores
como:
- los datos de entrada del programa
- la calidad del código objeto generado por el compilador
- la naturaleza y rapidez de las instrucciones de máquina utilizadas
- la complejidad en tiempo del algoritmo base del programa
El tiempo de ejecución debe definirse como una función que depende de la entrada; en particular, de su tamaño. El tiempo requerido por un algoritmo expresado como una función del tamaño de la entrada del problema se denomina complejidad en tiempo del algoritmo y se denota T(n). El comportamiento límite de la complejidad a medida que crece el tamaño del problema se denomina complejidad en tiempo asintótica. De manera análoga se pueden establecer definiciones para la complejidad en espacio y la complejidad en espacio asintótica.
El tiempo de ejecución depende de diversos factores. Se tomará como más relevante el relacionado con la entrada de datos del programa, asociando a un problema un entero llamado tamaño del problema, el cual es una medida de la cantidad de datos de entrada.
Figura 1.1 Características del programa ideal
En muchos casos, la complejidad de tiempo de un algoritmo es igual para todas las instancias de tamaño n del problema. En otros casos, la complejidad de un algoritmo de tamaño n es distinta dependiendo de las instancias de tamaño n del problema que resuelve. Esto nos lleva a estudiar la complejidad del peor caso, mejor caso, y caso promedio.
Para un tamaño dado (n), la complejidad del algoritmo en el peor caso resulta de tomar el máximo tiempo (complejidad máxima) en que se ejecuta el algoritmo, entre todas las instancias del problema (que resuelve el algoritmo) de tamaño n; la complejidad en el caso promedio es la esperanza matemática del tiempo de ejecución del algoritmo para entradas de tamaño n, y la complejidad mejor caso es el menor tiempo en que se ejecuta el algoritmo para entradas de tamaño n. Por defecto se toma la complejidad del peor caso como medida de complejidad T(n) del algoritmo.
Aún cuando son los programas que los llegan realmente a consumir recursos computacionales (memoria, tiempo, etc.) sobre una máquina concreta, se realiza el análisis sobre el algoritmo de base, considerando que se ejecuta en una máquina hipotética.
La complejidad de un progranma depende de:
Complejidad temporal: Se define como el tiempo que tarda un algoritmo en una entrada de tamaño n.
La complejidad en el caso peor proporciona una medida pesimista, pero fiable.
Dado que se realiza un estudio teórico de la complejidad, ignorando aspectos como las características de la máquina y el compilador, se tiene en cuenta que las diferencias en eficiencia se hacen más significativos para tamaños grandes de los datos de entrada se analiza la complejidad en términos de su comportamiento asintótico, dejando de lado la forma exacta de la función de complejidad.
1.3 Aritmética de Notación O (O grande)
Decimos que un algoritmo tiene un orden O(n) si existen un n0 y un c, siendo c>0, tal que para todo n>=n0, T(n)<=c*f(n).
La relación O denota una dominancia de funciones, en donde la función f está acotada superiormente por un múltiplo de la función g (f es dominada por c.g(n)). Así, la expresión f=O(g) refleja que el orden de crecimiento asintótico de la función f es inferior o igual al de la función g.
Ejemplo 1.1:- Dominancia de Funciones - Notación O
Sea f(n) = 3*n^3 + 2*n^2 y g(n) = n^3, con n>0. Se dice que f es dominada por g(n), dado que existe una constante c (c=5) tal que f(n) <= c*g(n) ==> 3*n^3 + 2*n^2= O(n^3)
A continuación se enumeran las propiedades básicas de la notación O:
Reglas de Cálculo de Complejidad:
- El tiempo de ejecución de cada sentencia simple, por lo común puede tomarse como O(1). Algunas operaciones matemáticas no deben ser tratadas como operaciones elementales. Por ejemplo, el tiempo necesario para realizar sumas y productos crece con la longitud de los operandos. Sin embargo, en la práctica se consideran elementales siempre que los datos que se usen tengan un tamaño razonable.
- El tiempo de ejecución de una secuencia de proposiciones se determina por la regla de la suma. Es el máximo tiempo de ejecución de una proposición de la sentencia.
- Para las sentencias de bifurcación (IF,CASE) el orden resultante será el de la bifurcación con mayor orden.
- Para los bucles es el orden del cuerpo del bucle sumado tantas veces como se ejecute el bucle. Este tiempo debería incluir: el tiempo propio del cuerpo y el asociado a la evaluación de la condición y su actualización, en su caso. Si se trata de una condición sencilla (sin llamadas a función) el tiempo es O(1), que no es relevante para al cálculo asintótico. Cuando se trata de un bucle donde todas las iteraciones son iguales, entonces el tiempo total será el producto del número de iteraciones por el tiempo que requiere cada una.
- Para los bucles anidados el orden corresponde a la multiplicación del orden del bucle interno por el orden del bucle externo.
- El orden de una llamada a un subprograma no recursivo es el orden del subprograma.
Algunos de órdenes de complejidad que se presentan con frecuencia son:
En la figura 1.2 se presenta una comparación entre los principales órdenes de complejidad. Es de destacar el excesivo costo que representa una complejidad de orden 2^n, frente a la estabilidad de la complejidad logarítmica
Figura 1.2 Comparativo entre órdenes de complejidad
Ejemplo 1.2:- Análisis de complejidad - Bucles for - Orden Polinómico
for (i = 0; i < n-1; i++) {
indice = i;
for (j = i+1; j < n; j++) {
if (A[j] < A[indice])
indice = j;
temporal = A[indice];
A[indice] = A[i];
A[i] = temporal;
};
}
Este algoritmo es de complejidad O(n^2), dado que las intrucciones al interior del bucle for interno son de orden O(1), por lo que el bucle tendrá una complejidad O(n) frente a una complejidad del bucle externo de O(n), el algoritmo tendría una complejidad de O(n^2)=O(n){bucle externo}*O(n){bucle interno}
Ejemplo 1.3:- Análisis de complejidad - Estructura Condicional - Orden Polinómico
if (A[0][0] == 0)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
A[i][j] = 0;
else
for (k =0; k < n; k++)
A[k][k] = 1;
Este algoritmo es de complejidad O(n^2), dado que las intrucciones al interior de la rama if corresponden a un orden O(n^2) (dos bucles anidados)y la rama else una complejidad, proporcionada por bucle interno, de O(n). (O(if) > O(else))
Ejemplo 1.4:- Análisis de complejidad - Bucle - Orden Logarítmico
while (x <= n)
{
x = 2 * x;
contador++;
}
Este algoritmo es de complejidad O(log2(n)). Las intrucciones al interior del bucle tienen complejidad de O(1), sin embargo el orden del bucle esta definido por el valor que toma una de sus variables (x), por lo tanto, se debe analizar el tamaño del bucle a partir de los valores de esta variable. Como x = 2*4*8*16*32*... -> n <= 2^k -> k = eis(log2(n)) (entero inmediatamente superior), k representa el número de veces que se ejecuta el bucle, por lo tanto el algoritmo tiene complejidad de orden O(log2(n)).
El cálculo de las constantes de la función de tiempo es importante cuando se comparan algoritmo de orden similar, las constante pueden determinar cual es el algoritmo de mejor compoprtamiento.
La misma idea que se utiliza para medir la complejidad en tiempo de un algoritmo se utiliza para medir su complejidaden espacio. Decir que un programa es O(n) en espacio significa que sus requerimientosde memoria aumentan uamentan proporcionalmente con el tamaño del problema. Esto es, si el problema se duplica, se necesita el doble de memoria. Del mismo modo, para un programa de complejidad O(n^2) en espacio, la cantidad de memoria que se necesita para almacenar los datos crece con el cuadrado del tamaño del problema: si el problema se duplica, se requiere cuatro veces más memoria. En general, el cálculo de la complejidad en espacio de un algoritmo es un proceso sencillo que se realiza mediante el estudio de las estructuras de datos y su relación con el tamaño del problema.
Los requerimientos estáticos de memoria se refieren al tamaño de los objetos que resuelven el problema. El espacio requerido por los objetos de datos de los tipos primitivos y de los tipos estructurados de los lenguajes de programación, son fácilmente calculables, dependiendo de la implementación del mismo. Se les conoce como objetos de datos estáticos porque la cantidad de espacio que requieren es deducible en su declaración, por lo que ya en compilación (si el lenguaje es compilado), el compilador conoce cuánta memoria requerirán, que será invariante a lo largo del alcance del objeto.
El análisis de los requerimientos dinámicos de
memoria es relativo a los lenguajes que proveen mecanismos de asignación
dinámica de la misma. En este caso, la complejidad en espacio viene dada
por la cantidad de objetos existentes en un punto del programa, según
las reglas de alcance. Así, la cantidad de espacio requerido no será
la sumatoria de todas las declaraciones de datos, sino la máxima cantidad
de memoria en uso en un momento dado
de la ejecución del programa.
El problema de eficiencia de un programa se puede plantear como un compromiso entre el tiempo y el espacio utilizados. Por eso, la etapa de diseño es tan importante dentro del proceso de construcción de software, ya que va a determinar en muchos aspectos la calidad del producto obtenido.
Un algoritmo será más eficiente cuanto menos recursos computacionales consuma: tiempo y espacio de memoraia requerido para su ejecución.
La eficiencia de un algoritmo se cuantifica en términos de su complejidad temporal (tiempo de cómputo del programa) y su complejidad espacial (memoria que utiliza el programa durante su ejecución).
¿Para que emplear tiempo en diseñar algoritmos eficientes si los ordenadores tienen cada vez más recursos computacionales?
Tabla 1.1 Tiempo de Ejecución algoritmo de orden 2^n
| n |
Tiempo |
| 10 |
Aprox. 0.1 seg |
| 20 |
Aprox. 2 min |
| 30 |
> 1 día |
| 40 |
> 3 años |
Tabla 1.2 Tiempo de Ejecución algoritmo de orden 2^n
| n |
Tiempo |
| 50 |
35 años |
La seleccción de un algoritmo es un proceso es un proceso en el que se deben tener en cuenta muchos factores, entre los cuales podemos destacar los siguientes:
El contenido de esta página esta basado en el material disponible en: