En la actualidad “casi” toda la información numérica es tratada con dispositivos electrónicos y/o computadores y uno de los aspectos principales en ese proceso es el estudio de la Complejidad Computacional.
Gottfried Leibniz publica en 1.686 “Discurso sobre metafísica”, en él trata de distinguir los hechos que están regidos por leyes de los que no lo están, asume la idea de que:
“Mas cuando una regla es demasiado complicada, lo que está conforme con ella pasa por irregular. Así, puede decirse que, de cualquier manera que Dios hubiese creado el mundo, hubiera sido siempre regular y de un cierto orden general. Pero Dios ha escogido el que es más perfecto, es decir, el que es más simple en hipótesis y más rico en fenómenos, como podría ser una línea geométrica cuya construcción fuese fácil y sus propiedades y efectos admirables y de gran amplitud. “.
También se podría tomar la frase que muchos conocen como la “Navaja de Ockham”, la explicación más sencilla es probablemente la explicación correcta”.
Son buenas ideas para abordar el método que resuelve un problema, nosotros diríamos: no ahagamos un algoritmo más largo, complejo o difícil de explicar que el mismo problema.
Complejidad.
La solución de un problema exige un método de resolución (algoritmo) y una codificación (programa). La importancia del algoritmo es esencial, mientras que la codificación pasa a segundo nivel.
La Complejidad Computacional tiene como finalidad la creación de mecanismos y herramientas capaces de describir y analizar la complejidad de un problema, su algoritmo y de identificar la eficiencia del algoritmo con independencia de la potencia de la máquina. Se consideran dos puntos esenciales para su valoración:
Tiempo. Número de pasos por tiempo de ejecución del paso (instrucción, función, …), o tiempo total de ejecución.La ejecución de un programa en función de N (Tamaño por número de datos), se denomina T(N), esta función se puede medir físicamente (ejecutamos el programa cronómetro en mano, o calculamos sobre el código contando los pasos ejecutados y los multiplicamos por el tiempo requerido por paso). Lo más fácil es poner un marcador de tiempo al inicio del proceso y registrar el tiempo al finalizar, con la diferencia ya lo tenemos.
Espacio. Cantidad de memoria y/o almacenamiento necesario. Lo más rápido para ejecutar un proceso, en un computador, es tener la información en memoria (RAM), esto implica conocer hasta dónde llegarán sus necesidades, pues el proceso puede abortar y perder la información y tiempo procesados. Si la parte crítica está en el volumen de información (cantidad de ficheros, datos, …) estudiaremos los dispositivos de almacenamiento (discos de estado sólido, disco virtual en RAM …)
A partir de ahora debemos introducir otro concepto, “el problema de decisión”, que es aquel en el cual las respuestas posibles son Si o No y se clasifican en función de la:
Computabilidad. El problema es:
- Decidible “Resoluble algorítmicamente”: Si existe un procedimiento mecánico (MT) que lo resuelva. Además, la MT debe detenerse para cualquier entrada.
- Parcialmente Decidible “Reconocible”: Si existe un procedimiento mecánico (MT) que lo resuelva. Además, la (MT) debe detenerse para aquellas entradas que son una solución correcta al problema.
- No Decidible Los problemas computables (decidibles) tienen un algoritmo que los resuelve, para cualquier valor de entrada se obtiene una solución al problema. Los problemas no computables (indecidibles) no tienen un algoritmo que los resuelva.
Simplificando, la complejidad computacional está determinada por el número de comparaciones y de asignaciones entre el conjunto de elementos que se realiza en una implementación del algoritmo.
Notación.
En computación/informática se utiliza la notación asintótica para representar la complejidad (eficiencia o el rendimiento) de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada, facilitando la comparación de las velocidades de distintos de ellos y por tanto, dar una idea de cuánto tiempo llevará ejecutar el mismo.
Antes de escribir un algoritmo debemos pensar en el tiempo que tardará en solucionar el problema y conocer cuál es el tiempo de solución razonable. Los tiempos que se consideran, “razonables”, son los que están limitados por un polinomio (p), utilizándose en la mayoría de los casos la notación de E. Landau, “O“, para medirlos, su forma es:
O(p)
Si un algoritmo tiene complejidad O(p(n)) significa que al ejecutarlo en una computadora con los mismos datos, pero con valores incrementales de n, los tiempos resultantes de ejecución serán siempre menores que | p(n) |.
Respecto de los límites, el límite superior de un problema es el coste asintótico del algoritmo más rápido conocido que lo resuelve, representándolo con la llamada notación “Big-O“, anticipa la mayor cantidad de tiempo que un algoritmo necesita para resolver un problema para cualquier entrada de tamaño n. El límite inferior, el menor coste para cualquier algoritmo, incluidos los aún no inventados, se denotan como “Big-Ω Omega”. Una vez que los límites superior e inferior se encuentran, sabemos que ningún algoritmo futuro puede ser más eficiente. El promedio se representa con la notación “Big-Θ Theta”, la cota ajustada asintótica.
El peor tiempo de ejecución de un algoritmo nos da un límite superior en la complejidad computacional. Si el tiempo de ejecución crece de forma exponencial, esta es la peor noticia que podemos tener.
Notación de los principales órdenes de complejidad:
- Constante O (1). Es una operación simple, unitaria, por ejemplo: Asignar un valor a una variable, añadir un elemento a un vector, etc.
- Logarítmica O (Log n). Se produce cuando no se crece al mismo nivel que n, un ejemplo puede ser la búsqueda binaria, también la siguiente instrucción: for( int i=0; i < n; i *= 2) { operación constante O(1) }.
- Lineal O (n). Aplicable a los bucles (n vueltas) que tienen dentro una declaración O (1). Su complejidad para el ciclo completo es n * O (1), lo que equivale a O (n).
- Casi lineal O (n * Log n). Es una combinación de un bucle n y otro interno O (Log n). Un ejemplo claro estaría en el algoritmo de ordenación Quick sort.
- Cuadrática O (n 2). Aplicable a bucles anidados, el primer bucle se ejecuta n veces y el segundo (interno) también n veces. Por lo tanto, la instrucción en el bucle interno se ejecuta un total de n * n veces, algo no deseable para grandes conjuntos de datos (n).
- Exponencial O (2 n ). Itera a través de todos los subconjuntos de los elementos de entrada. Un ejemplo claro son los algoritmos de fuerza bruta, o uno más biológico: El crecimiento de la población de conejos en Australia, en 1.859 importaron 24 conejos, a los seis años eran 22 millones. (Ver el ejemplo de Fibonacci).
- Factorial O(n!). Itera a través de todas las permutaciones de los elementos de entrada.
| Orden | Nombre |
| O(1) | Constante |
| O(log n) | Logaritmica |
| O(n) | Lineal |
| O(n log n) | Casi Lineal |
| O(n2) | Cuadrática |
| O(2n) | Exponencial |
| O(n!) | Factorial |
Ejemplo.
Cuando abordamos un problema tratamos de identificar cuántos elementos n pueden intervenir en su solución y cuánto tiempo podemos tardar en solucionarlo. En base a la experiencia y conocimiento de la persona que aborde el problema, encontraremos más de una forma de resolverlo y una o pocas de esas formas serán las más eficientes. Esto implica encontrar un algoritmo para el cual el orden de complejidad temporal sea mínimo, el cálculo de esta complejidad temporal nos dirá cuántos ciclos/cálculos deberemos realizar para su solución.
Cuando hayamos identificado el orden de magnitud del problema, podremos identificar cuanto aumenta la cantidad de tiempo requerido para resolverlo cuando crece en tamaño (n). No se tiene en cuenta la variable Espacio.
Recordemos que la potencia de la máquina no debe influenciar y es independiente a la evaluación del algoritmo que resuelve el problema, también que n debe ser lo suficientemente grande para que haya diferencias:
Complejidad cuadrática O(nx):
Tenemos dos algoritmos, Algo1 y Algo2, que actúan sobre n datos, ambos hacen S sumas, P productos, D divisiones y C comparaciones, de tal forma que lo podemos ver de la siguiente forma:
Cuando n tienda a infinito, Algo1 será más rápido en S, D y C. Algo2 sólo será más rápido en P. Diremos que A1 tiene una complejidad de orden n3, lo indicaremos como O(n3) y A2 tiene una complejidad de orden n6, lo indicaremos O(n6). De esta forma podemos comprobar que no existe la necesidad de codificar un programa para comprobar su eficiencia.
Complejidad lineal O(n):
Debemos calcular el importe total de una factura para un cliente que puede contener n albaranes de entrega de mercancía por semana. La dimensión es la cantidad de albaranes y la suma, pues eso, la suma de sus importes. Supongamos que una computadora ejecuta el siguiente algoritmo para calcular el importe total:
- Leemos un albarán.
- Sumamos el importe del albarán a la variable suma.
- Si existen más albaranes pasamos a 1
- Terminamos.
Si el cliente tiene un sólo albarán, la dimensión es 1 y los pasos realizados son (3) : 1, 2 y 3. El valor de la complejidad temporal sería ct = 3, para n = 1.
Cuando tengamos 2 albaranes los pasos serían n*ct → 2 * 3 = 6. La respuesta es que la complejidad temporal del algoritmo está dada por n (es lineal ), su representación sería O (n).
Visto así es fácil y simple, pero imaginemos que el paso (2) contiene 10 cálculos, que la cantidad promedio de albaranes son 6, el nº de clientes 1.000 y la facturación se realiza mensualmente: n*ct 6*12= 72 * (1.000 clientes) * (4 semanas) = 288.000 operaciones, la perspectiva cambia, pero es asumible.
Ahora somos “El Corte Inglés”, tenemos ± 2,5 Millones de referencias (artículos), 2 Millones de clientes que compran un promedio de 2 productos al mes en compras distintas, los números son: 2*12= 24 * 2.000.000 = 48.000.000 de operaciones, la cosa empieza a cambiar. Ahora somos “Walmart” con ± 23,5 millones de productos a la venta o “Amazon” con ± 332 millones, esto comienza a convertirse en algo muy muy grande. Afortunadamente sabemos que tiene un crecimiento lineal y podemos tomar las medidas sin llevarnos las manos a la cabeza.
Complejidad Casi Lineal O(n log n):
En este caso tomamos un ejemplo referente a la ordenación de vectores, Mergesort. A grandes rasgos, el algoritmo fusiona 2 subvectores (ordenados) de un vector principal con n elementos. El algoritmo es recursivo, dividiendo cada uno de los subvectores en otros dos que a su vez se vuelven a dividir en otros dos,… que finalmente deberán ser fusionados
Dos subvectores de un vector de tamaño n necesita (n – 1) comparaciones para ser ordenado. La función de complejidad temporal de la fusión está dada por T(n): n – 1.
Supongamos que tenemos un vector de 80.000 elementos, la fusión de sus dos subvectores de 40.000 elementos nos costará 80.000 – 1 = 79.999 comparaciones. Continuando de forma recursiva veremos que cada vez que dividimos un vector en subvectores, necesitaremos n – 1 operaciones para fusionarlas más tarde.
Para obtener la complejidad deberemos saber cuántas veces podemos dividir los vectores (sub) hasta que ya no se puedan dividir, matemáticamente es log2 n, por lo que la función de complejidad de tiempo es T (n): (n-1) * log2 n, la notación generalizada es O (n * log n).
Clases.
En función de la complejidad del problema se utilizan distintas nomenclaturas, las cuatro más comunes son:
P. Son los problemas fáciles o tratables y pueden resolverse en tiempo polinomial.
NP. Es una clase que incluye a P y donde se encuentran los problemas difíciles que pueden llegar a ser intratables.
NPcompletos. Son los problemas que tardan una cantidad exponencial de tiempo llegando a ser intratables.
PSPACE. Es la clase donde los problemas pueden resolverse en una cantidad de espacio polinomial.
Hay identificadas más de 500 clases de complejidad, algo que sobrepasa el alcance de este artículo pero todas ellas están dentro de los siguientes grupos:
De comunicación. Se ocupa de la cantidad de datos que deben intercambiarse entre las partes que cooperan para calcular una función cuya entrada se divide entre ellas.
Jerárquica. Existen clases que se definen como uniones de jerarquías.
No uniforme. Permite el uso de un algoritmo diferente para cada longitud de entrada.
En esta tabla describimos algunas de ellas:
| Símbolo | Comentario | Restricción de recursos | Modelo de cómputo |
|---|---|---|---|
| DTIME(f(n)) | También se la denomina TIME(f(n)) , resuelve el problema en tiempo O(f(n)) y espacio ilimitado. | Tiempo f(n) | Determinista |
| EXPSPACE | Son el conjunto de los problemas de decisión donde poly(n) es una función polinomial sobre n. Cuando se restringe poly(n) como una función lineal, la clase resultante se denomina ESPACE. | Espacio 2poly(n) | No determinista |
| L | Son el conjunto de los problemas de decisión donde la solución, si existe, es única. (No se cuenta el tamaño de la entrada). La clase L está contenida en NL y NL tambien está contenida en PSPACE | Espacio O(log n) | Determinista |
| NEXPSPACE | Son el conjunto de los problemas de decisión donde poly(n) es una función polinomial sobre n. Cuando se restringe poly(n) como una función lineal, la clase resultante se denomina ESPACE. | Espacio 2poly(n) | No determinista |
| NL | Son el conjunto de los problemas de decisión donde la solución, si existe, es única. (No se cuenta el tamaño de la entrada). La clase NL está contenida en PSPACE | Espacio O(log n) | Determinista |
| NP | La propone Stephen Cook en 1.971 y L. A. Levin en 1.973, “detrás del telón de acero”. NP es el conjunto de todos los problemas donde las respuestas a las instancias es “sí” y tienen pruebas verificables de manera eficiente . Más precisamente, estas pruebas son verificables mediante cálculos determinísticos que se pueden realizar en tiempo polinomial . | Tiempo poly(n) | Determinista |
| P | La definió Alan Cobham en 1.964 y al mismo tiempo Jack Edmonds en 1.965. Son problemas tratables, es decir se pueden resolver en un tiempo razonable,(ordenaciones, búsquedas, … ). P está contenido en EXPTIME.También se le denomina PTIME o DTIME | Tiempo poly(n) | No determinista |
| PSPACE | Se resuelve en espacio de polinomios y tiempo ilimitado. | Espacio poly(n) | Determinista |
En el siguiente gráfico, mantenido por Greg Kuperberg, podemos ver las relaciones de las clases de complejidad.
Diagrama clases de complejidad