Complejidad computacional: ¿qué es?

Hola a todos!

Estoy redactando un post donde retomo el problema de generar o determinar si un número entero dado es primo, ya que creo que el post original da mucho de que hablar y no lo he hecho en bastante tiempo. Sin embargo, en el post donde hablo del problema originalmente, se llegó a debatir mucho sobre su eficiencia o complejidad, pero parece que esto metía mucho ruido y no ha sido clarificado del todo, al menos en este blog.

Así que decidí escribir este post adicional, donde pretendo explicar de manera simple y superficial qué es la complejidad computacional, o para fines prácticos, qué es la complejidad de un algoritmo.

---

Vamos a empezar con un simple ejemplo. Supongamos, por ejemplo que queremos calcular una potencia de 2 a un número entero positivo cualquiera. Es decir, queremos crear un programa de computadora que nos diga cuál es el resultado de 2^a, con a un entero positivo.

Una primera solución, sería la siguiente:

Power(Integer a)
Begin
    Integer x <- 2
    while(a > 1) do
        x <- 2 *x
        a <- a -1
    end
    return a
End

Llamemos a esta solución solución1. La solución es correcta; en cuanto a elevar 2 a a, lo hace correctamente. Entonces, ¿tiene algo de malo?

La mayoría de las arquitecturas, nos permiten hacer uso de una operación llamada corrimiento de bits. El corrimiento de bits, consiste en desplazar todos los bits de un registro del procesador en alguna dirección, a la izquierda o la derecha (tomando en cuenta si la arquitectura en cuestión es Big Endian o Little Endian). Por ejemplo, si tenemos una arquitectura Little Endian, donde la memoria representa los valores tal y cómo lo haríamos normalmente (el LSB es el que está al extremo derecho de número, escribiéndolo horizontalmente), supongamos que tenemos almacenado en memoria el valor o0100101 (37 en binario) en un registro del procesador y hacemos un corrimiento de 2 bits a la izquierda.

El resultado de dicho corrimiento dejaría al registro con el siguiente valor: 10010100 (148 en binario) Si nos ponemos a escribir más ejemplos cómo este, notaremos que ocurre un patrón: el corrimiento, cuando hace crecer el valor del número en su representación en los registros del procesador, equivale a multiplicarlo por la potencia de 2 a la número de bit corridos. En el caso anterior, teníamos 37 y lo corrimos 2 bits, entonces 2² = 4 y 37 *4 = 148, que fue el resultado del corrimiento.

El corrimiento de bits, cómo la multiplicación, negación o asignación, es una operación definida en el conjunto de instrucciones de la máquina (en casi todos los casos), por lo que podemos pensar que se realiza en una sola unidad de tiempo.

Los lenguajes de programación, incluso aquellos «temidos» y considerados cómo de «medio nivel» (si eso existe), cómo C, abstraen la representación numérica del procesador y simplemente podemos correr, suponiendo que todas las computadoras son little endian. Esta operación normalmente se usa con «>>» para corrimiento a la derecha y «<<» para corrimiento a la izquierda en la mayoría de los lenguajes: C, Java, Phyton, PHP…

Entonces, felizmente, podemos escribir el siguiente programa que resuelve el problema originalmente planteado: elevar un número entero positivo cualquiera a a otro b potencia de 2:

 Power(Integer a)
 Begin
    return 2 << --a {pow como el de súper Mario}
 End

Punto número 1 que reconocerán la mayoría de los programadores: es un programa muy pequeño comparado con el original. Punto número 2: es mucho más rápido. Llamemos a esta solución solución2. Aquí retomamos la cuestión de la complejidad.

---

No sólo el número de instrucciones cambia en el algoritmo, sino que también cambia el número de instrucciones que se van a ejecutar. ¿qué quiere decir esto?

Supongamos que a = 5.

Según la solución1:

1. Creamos x.
2. Hacemos x = 2.
3. Entramos a un ciclo, preguntando si a = 5 > 1.
4. Esto es verdad y continuamos en el ciclo.
5. hacemos x = 2 *x que es x = 2 *2 = 4
6. hacemos a = a -1 que es a = 5 -1 = 4.
7. Repetimos el ciclo, preguntando si a = 4 > 1.
8. Esto es verdad y continuamos en el ciclo.
9. hacemos x = 2 *x que es x = 2 *4 = 8
10. hacemos a = a -1 que es a = 4 -1 = 3
11. Repetimos el ciclo, preguntando si a = 3 > 1.
12. Esto es verdad y continuamos en el ciclo.
13. hacemos x = 2 *x que es x = 2 *8 = 16
14. hacemos a = a -1 que es a = 3 -1 = 2
15. Repetimos el ciclo, preguntando si a = 2 > 1.
16. Esto es verdad y continuamos en el ciclo.
17. hacemos x = 2 *x que es x = 2 *16 = 32
18. hacemos a = a -1 que es a = 2 -1 = 1
19. Repetimos el ciclo, preguntando si a = 1 > 1.
20. Esto es falso, y salimos del ciclo.
21. Devolvemos el valor de a (32 que en efecto es 2⁵ cómo podrá corroborar cualquiera con suficiente papel, lápiz y paciencia o una calculadora).

Contamos 21 instrucciones sólo para hacer 2⁵, ¿qué pasaría si ahora a = 88888? El algoritmo sería linealmente más lento. ¿Qué quiere decir esto?

Para saber cuánto tiempo se va a tardar un algoritmo en ejecutarse, no es necesario probarlo con todas las posibles entradas (por ejemplos, todas las combinaciones de enteros positivos de 64 bits para a y b). Si no que contamos las instrucciones en el algoritmo. Para esto usamos las operaciones elementales.

---

Las operaciones elementales, son un conjunto de operaciones que se considera se realizan en un tiempo constante y bien definido; aunque no necesariamente todos los procesadores y arquitecturas lo hacen en sólo un tiempo (u operación) en la vida real.

A continuación, va una lista de las operaciones elementales más comunes (indicando el operador con el que se utiliza en varios lenguajes de programación):

• . Acceso. Accede a una localidad de memoria. Esto incluye la lectura de variables, constantes e invocación de rutinas.
  • ++ Incremento. Suma 1 a la variable (o registro) al que se aplique.
• — Decremento. Resta 1 a la variable (o registro) al que se aplique.
• ! Negación. Invierte el valor de un booleano.
• >> Corrimiento de bits a la derecha.
• << Corrimiento de bits a la izquierda.
• (<tipo de datos>) Cast. Convierte un tipo de datos en otro.
• new Instanciación. Crear un objeto (POO).
• * Producto. Multiplica dos números.
• / División. Divide dos números.
• % Módulo. Devuelve lo que restaría de dividir un número entre otro. Por ejemplo 5 % 2 = 1.
• + Suma. Suma dos números.
• – Resta. Resta dos números.
• < Menor que. Indica si un número tiene un valor menor que alguno otro.
• > Mayor que. Indica si un número tiene un valor mayor que alguno otro.
• <= Menor o igual que. Indica si un número tiene un valor menor o igual que alguno otro.
• >= Mayor o igual que. Indica si un número tiene un valor mayor o igual que alguno otro.
• == Igual a. Indica si dos valores son iguales.
• != Diferente de. Indica si dos valores son diferentes.
• && AND. Devuelve verdadero si y sólo si los booleanos que compara son verdaderos. En otro caso, devuelve falso.
• || OR. Devuelve verdadero si alguno o ambos de los booleanos que compara es verdadero. Si ambos son falsos, devuelve falso.
• = Asignación. Asigna un valor.
• Saltar a una dirección de memoria también es una operación elemental. Esto incluye entrar en un if, un while, for, un goto, llamar a una función, devolver un valor (return), etc.

Conociendo ahora las operaciones elementales, analicemos el caso de la solución2.

---

Resolvamos exactamente el mismo problema, 2⁵ utilizando la solución2. De acuerdo a la misma, el procedimiento es el siguiente:

1. Decrementamos el valor de a en una unidad, esto es a = 5 -1 = 4.
2. Corremos el valor de 2 (00000010) 4 veces a la izquierda (00100000 = 32).
3. Devolvemos el valor obtenido (00100000 = 32).

¡Sólo 3 operaciones contra las 21 de la solución1! Además, en la solución 1 hicimos trampa de alguna manera, ya que al no conocer las operaciones elementales, contábamos en una sola operación cosas cómo while(a > 1), donde hay 3 operaciones elementales: un salto en el flujo del programa (while), un acceso a memoria (el valor de a) y una comparación (>). También en las operaciones cómo a = a -1 se hizo un conteo inadecuado, ya que a diferencia de a–, a = a -1 no es una operación elemental, si no otras 3: el acceso al valor de a, la resta con 1 y la asignación del resultado de la resta a la dirección de a.

La solución1 es mucho más lenta que sólo 21 operaciones, pero la solución2 sólo hace 3 operaciones.

Además, note que el número de veces que se repite el ciclo de la solución1 depende de a. Prácticamente, el ciclo ocurre tantas veces cómo el valor de a. En general, si a = n, entonces el ciclo se repite n -1 veces. A esto se le llama tiempo de complejidad lineal, pues el tiempo de ejecución del algoritmo, depende de a en forma lineal.

Por otro lado,  la solución2 sólo ejecuta 3 operaciones elementales, sin importar el valor de a. A esto se le llama tiempo de complejidad constante, pues el tiempo de ejecución del algoritmo será siempre el mismo, sin importar los valores de entrada que le demos.

En general, queremos diseñar algoritmos de la menor complejidad posible, pero esto no es siempre posible. En todo caso, siempre hay que buscar la forma de hacer que nuestro algoritmo ejecute la menor cantidad de operaciones elementales en función de su vector de valores de entrada.

Espero que hasta aquí pueda apreciar la importancia de la complejidad: un algoritmo es eficiente si su complejidad es eficiente, esto incluye (de acuerdo a los teóricos) a los algoritmos constantes, lineales y superlineales (el tiempo de ejecución es del orden de n*log(n), la base del logaritmo es indiferente, aunque normalmente es 2). A partir de complejidad cuadrada (del orden de n²), se consideran los algoritmos cómo ineficientes, aunque en la práctica existen muchos algoritmos de orden de hasta n⁴ que se ejecutan considerablemente rápido.

Para hacer un poco más clara la importancia de los tiempos de ejecución en función de los valores de entrada (o dicho en otras palabras la complejidad del algoritmo), veamos el siguiente ejemplo:

Haremos una búsqueda en un arreglo de enteros. Considere que el arreglo es representado por una variable de nombre «haystack» y el entero que queremos buscar es representado por la variable «needle». Una de las formas más inmediatas/intuitivas de hacer la búsqueda es mediante una exploración completa: revisar cada localidad de memoria en el arreglo e indicar si en algún momento encontramos la ajuga en el pajar. En pseudocódigo; esto se ve así:

Search(Integer needle, Integer[] haystack)
Begin
    FOREACH (Integer straw IN haystack) DO
        IF (straw = needle) THEN
            RETURN true;
        END IF
    END FOR
    RETURN false;
End

Si nos detenemos a analizar el número de instrucciones que se van a ejecutar en este programa, dependen completamente del tamaño del arreglo «haystack» (pajar). Si el arreglo es de tamaño 1, necesitaremos hacer una sola comparación contra needle (aguja). Si el arreglo es de tamaño 3 y en efecto needle no existe en haystack, deberemos hacer todas las 3 comparaciones.

En general, este tipo de búsquedas en estructuras lineales; como los arreglos, sin poder suponer que están ordenadas en alguna forma, tardan tanto en ejecutarse como el tamaño del arreglo. Es posible que el tiempo de ejecución de un algoritmo dependa de más de un parámetro; y que dependa de más de una forma: por ejemplo, si queremos ordenar los números en haystack de menor a mayor comparando la primer localidad de memoria contra todas las demás y la segunda con la todas las demás…

Sort(Integer[] array)
Begin
    FOREACH (Integer to_compare IN array) DO
        FOREACH (Integer all_others IN array) DO
            IF (to_compare < all_others) THEN
                Swap(all_others, to_compare)
            ENDIF
        ENDFOR
    ENDFOR
End

El programa anterior describe en pseudocógido la idea que sugería hace un momento, donde la instrucción «Swap» de alguna forma realiza el intercambio de la localidad «all_others» con «to_compare» para que el arreglo «array» quede al final ordenado de menor a mayor.

Esta forma tan intuitiva e inmediata de realizar un ordenamiento es ineficiente. Y es un ejemplo de un algoritmo con tiempo de ejecución de orden cuadrado; pues los dos FOR dependen del tamaño de array, y uno se repite por cada iteración en el primero; así que por cada elemento en array, hay que recorrer todo array y así el número de instrucciones es el cuadrado del tamaño de array.

Esto es solo un pequeño esbozo de lo que son las categorías de complejidad computacional. La categoría más «simple», es denominada P; de polinomial. Contiene a todos los algoritmos que se ejecutan en algún orden de complejidad de tiempo cuya función puede quedar acotada por un polinomio.

Los dos ejemplos anteriores están en P, ya que por ejemplo; la búsqueda tiene complejidad de tiempo lineal, que depende de n directamente y esto es por supuesto acotado por un polinomio de grado 1. El ordenamiento queda acotado de la misma forma por un polinomio de segundo grado.

Arriba de P, tenemos NP. No voy a entrar en detalle de lo que significa un programa «no determinista»; ya que puede resultar confuso para algunos lectores. Sin embargo, es un tema muy interesante y recomendaría a todos los curiosos que busquen bibliografía académica al respecto (libros de teoría de la computación son un buen punto de inicio).

A grandes rasgos; un programa no determinista, se caracteriza por contar con puntos donde puede divergir a varias opciones arbitrariamente. Imagine un IF donde podemos ir tanto al THEN como al ELSE simultáneamente y sin mayor contrariedad… Y sí, esto tiene que ver con la computación cuántica.

Hay muchos problemas que se salen de la categoría P (polinomial), pues si tiempo de ejecución no puede ser modelado por ningún polinomio, sino por funciones que crecen más rápido: como las exponenciales o los factoriales; y algunas de estos problemas que se salen de P pueden resolverse con algoritmos que pertenecen a la clase NP.

Un; a mi gusto, excelente ejemplo de este tipo de problemas, es el problema de las torres de Hanoi. Las torres de Hanoi, son un juego propuesto por el matemático francés Èduard Lucas; quien al parecer inventó la leyenda de los monjes que tenían que mover 1 disco al día.

El problema de las torres de Hanoi es bastante divertido; consiste en lo siguiente:

• Se cuenta con tres postes (palos) y n discos. n por supuesto debe ser un número entero no negativo; o natural para los cuates.
• Cada disco tiene un radio único.
• Inicialmente, todos los discos están apilados en el mismo poste.
• Inicialmente, la torre original de discos; está ordenada de mayor a menor, contando a partir de la base de la torre (el disco más pequeño está hasta arriba).
• El objetivo del juego es mover todos los discos a alguno de los otros dos postes con las siguientes restricciones:
  • Sólo es posible mover un disco a la vez.
  • Sólo es posible colocar un disco de radio menor sobre otro de radio mayor; o en un poste vacío.

Resolver el problema de las torres de Hanoi; la mejor solución posible al problema, aquella con el menor número de pasos para reacomodar la torre en otro poste, resulta en un algoritmo (determinista) que tiene una función de complejidad de orden exponencial. Más precismente es: 2^n -1 (recuerde que n es el número de discos).

Es decir, si tenemos una torre de apenas 64 discos; tendremos que realizar 1.84467440737 x10¹⁹ movimientos. Si pudiéramos realizar cada movimiento en un milisegundo (imposible para cualquier persona), esto nos tomaría 1.84467440737 x10¹⁶ segundos, o lo que es lo mismo 3.07445734562 x10¹⁴ minutos = 5.12409557603 x10¹² horas = 213503982335 días = 30500568904.9 semanas = 7625142226.24 meses…

O lo que es lo mismo; 635’428,518.853 años ¡más de 600 millones de años! Ni siquiera el Sol tiene tanto tiempo… Y no existe forma de resolver Hanoi con una complejidad más amigable, esta es la mejor solución. Si está interesado en conocer más sobre el problema de las torres de Hanoi, cuento con notas al respecto que puede consultar en: http://www.nachintoch.mx/teaching/intro_data_structure/

---

Y ya para concluir, espero que con esta simple y breve explicación quede un poco más clara la idea de complejidad y porqué buscar soluciones más y más eficientes a los problemas es importante.

En particular; me interesa la cuestión de número primos, ya que los informados sabrán que encontrar primos es computacionalmente muy ineficiente; y este único hecho es lo que hace funcionar a nuestros sistemas criptográficos y todos los sistemas de seguridad informática, de alguna forma se basan en el hecho de que encontrar primos es computacionalmente difícil; lo que me parece maravilloso y peligroso. Si alguien encontrara formas eficientes de encontrar primos, se acaba lo poco que nos queda de privacidad en línea.

Espero haber aclarado algunas ideas y haber interesado algunos otros en aprender un poco más; ya sea en cuanto a la teoría de la computación, complejidad computacional, estructuras de datos o incluso seguridad informática (lo que puede incluir teoría de números y criptografía). Sin más, me despido. Trataré de seguir escribiendo algunos otros post que he tenido en borrador los últimos dos años.

Y no olviden que el límite es la imaginación… Y el tiempo que pueda tardar en ejecutarse un programa :S