Nerding about stuff I've found interesting

Los algoritmos existen para resolver un problema particular de manera eficiente pero ¿qué significa que un algoritmo sea eficiente? o tal vez más importante: ¿bajo qué métrica podemos concluir que una solución es más eficiente que otra? Responder éstas preguntas es el campo de estudio del análisis de algoritmos y el objetivo principal de este post.


Introducción

El análisis de un algoritmo suele reducirse a predecir la cantidad de recursos que éste ocupará durante su ejecución, por ejemplo ¿cuánta memoria RAM? ¿qué tanto ancho de banda? o incluso ¿qué otras partes del hardware utilizará y en qué medida?, aunque usualmente lo que nos interesa medir es el tiempo de ejecución. Por otro lado, al analizar un algoritmo suele interesarnos generalizar estas predicciones en lugar de obtener resultados exactos, por ejemplo: Si estuviéramos analizando un algoritmo que ordena números en una lista, preferimos obtener una idea general sobre la cantidad de recursos utilizados en función del tamaño la lista, en lugar de tener conocimiento de que dicho algoritmo de ordenamiento tarda 20 milisegundos en ordenar 1,000,000 de números en una computadora con un procesador de 3.7GHz y 4 GB de memoria RAM.

Con el propósito de la generalización en mente podemos también acordar que en los siguientes análisis que realizaremos vamos a asumir que todos los algoritmos correrán sobre una computadora modelo con memoria RAM y procesador en la cual cada una de las operaciones primitivas, como sumar, restar, leer un registro, etc, toma una cantidad constante de tiempo \(c\). De esta manera podemos medir el tiempo de ejecución de un algoritmo en términos de la cantidad de operaciones primitivas realizadas en lugar de usar unidades de tiempo concretas. Posteriormente, si se necesitara un predicción basada de una computadora particular, ésta se podría estimar fácilmente usando la cantidad de operaciones por segundo que dicha computadora es capaz de ejecutar.

Respecto al tamaño de la entrada, la generalización puede ser un poco más complicada ya que dependerá de la naturaleza del problema que estemos resolviendo, por ejemplo, en el caso del algoritmo de ordenamiento el tamaño de la entrada puede ser medido en la cantidad de elementos que se están ordenando, pero si nuestro algoritmo estuviera trabajando con grafos (gráficas, graphs), quizá sea mejor idea medir el tamaño por la cantidad de vértices y aristas. Usualmente es bastante obvio detectar la medida utilizada en el tamaño de la entrada.

El objetivo de este post es entender la complejidad computacional, usando generalización, partiendo del análisis detallado y minucioso de algunos algoritmos hasta llegar a los analísis más generales que nos permitirán categorizar los algoritmos con facilidad utilizando la notación asintótica, incluyendo \(O\) (Big-O), \(\Theta\) (theta) y \(\Omega\) (omega).


Haciendo cuentas

Ya que acordamos usar un modelo hipotético de computadora y que mediremos el tiempo de ejecución en la cantidad de operaciones primitivas, lo más natural sería comenzar a contar la cantidad de veces que nuestros algoritmos usan dichas operaciones y tal vez expresar dicha cuenta en forma de una función de costo que nos regrese el resultado en función del tamaño del problema, dígase \(T(n)\) .

Para entender mejor esta idea de hacer cuentas hagamos un ejercicio planteando un problema hipotético. El problema va así:

Dado un arreglo \(A\) de longitud \(n\), regresa un nuevo arreglo, también de longitud \(n\),  tal que el i-ésimo elemento contenga el resultado de sumar todos los elementos de la lista excepto él mismo.

O expresado en otras palabras:

Dado un arreglo \( A\) de longitud \(n\), \( A = \{a_1, a_2, a_3, …, a_n\}  \), regresar un arreglo \( B\) de longitud \(n\) que cumpla:

$$ \forall i \in [0, n-1], B[i] = -A[i] + \sum_{j=0}^{n-1}{A[j]} $$

Un ejemplo del input y output de de nuestro algoritmo sería el siguiente:

Input A:    [2, 5, 15, 13, 2, 13, 17, 1]
Output B:   [66, 63, 53, 55, 66, 55, 51, 67]

Ya que:   sum(A) = 68

Empecemos con la solución (algoritmo) más obvia: fuerza bruta. Lo que podemos hacer primero es crear un arreglo \(B\) de \(n\) elementos inicializado en \(0\) y luego por cada elemento en \(A\) recorremos \(A\) nuevamente generando así la suma descrita. La implementación en Python sería similar a la siguiente:

def array_difference(A):
    n = len(A)
    B = []
    for _ in range(n):
        B.append(0)

    for i in range(n):
        r = 0
        for j in range(n):
            if i != j:
                r += A[j]
        B[i] = r
    return B

Ya sé, es horrible, pero ten paciencia.

¡Ahora sí, vamos a comenzar a analizar nuestro desmadrito!

Recuerda que el objetivo del análisis es proveer una métrica de tiempo, dada en cantidad de operaciones, que sea dependiente al tamaño del problema. Entonces, lo primero que podemos hacer es obtener el costo y cantidad de veces que cada línea de nuestro código se ejecuta, y una vez hecho eso podemos dar la función \(T(n)\) que nos regrese la cantidad operaciones realizadas por nuestro algoritmo en función de \(n\) (el tamaño de la lista). Para hacer esto denotaremos \(c_i\) al tiempo constante que le toma a la computadora realizar la operación de la i-ésima línea. Finalmente, después de ir línea por línea asignando un costo \(c_i\) y revisando la cantidad de veces que son ejecutadas, obtendremos el siguiente chorizote:

$$ T(n) = c_2 + c_3 + n \cdot c_4 + n \cdot c_5 + n \cdot c_7 + n \cdot c_8 + n^2 \cdot c_9 + n^2 \cdot c_{10} + n^2 \cdot c_{11} + n \cdot c_{12} + c_{13}$$

La cuál también está horrible pero podemos reducirlo a:

$$ T(n) = n^2(c_9 + c_{10} + c_{11}) + n(c_4 + c_5 + c_7 + c_8 + c_{11} + c_{12}) + (c_2 + c_3 + c_{13})$$

O aún mejor:

$$T(n) = an^2 + bn + c $$

Donde las constantes \(a\), \(b\) y \(c\) dependen de los costos particulares de cada operación, pero, que aún así, se mantienen constantes. Lo anterior fue posible ya que trabajamos baja la suposición de que cada línea representa una operación primitiva de nuestro modelo de computadora, las cuales siempre toman tiempo constante, y finalmente nos permitieron obtener un polinomio bonito 💕.

¡CUIDADO! Es muy importante mencionar que haber trabajado bajo la suposición anterior fue un error que jamás se debe cometer ya que no existe una relación directa entre línea de código y operación primitiva de la computadora, por ejemplo, en la función \(T(n)\) asumimos muy aventuradamente que \(\mathrm{B.append}(0)\) tiene un costo constante en nuestro modelo hipotético, pero si \(\mathrm{B.append}(0)\) tuviera una función de costo del tipo \(an + b\) y además la mandáramos llamar dentro de nuestro primer for anidado (línea 10, por ejemplo), inadvertidamente convertiríamos nuestra función \(T(n)\) en una función de tipo \(an^3 + bn^2 + cn + d\), lo cual, y aprovechando nuestra actitud emprendedora, podemos adelantarnos a decir que: La función \(T(n) = an^2 + bn + c\) es una función cuadrática.

Pero antes de continuar hablando acerca de si es cuadrática, cúbica, exponencial o lo que sea, es importante que lo anterior quede muy claro y para asegurarnos de eso hagamos otro análisis detallado pero ahora con una solución más eficiente.

Para mejorar nuestra solución podemos proponer un nuevo algoritmo que primero calcule la suma de todos los elementos del arreglo \(A\) y después, al iterar en cada uno de ellos, solamente se reta cada elemento a la suma calculada asignando el resultado al i-ésimo elemento de \(B\). La implementación en Python luce así:

def efficient_array_difference(A):
    n = len(A)
    B = [0 for _ in range(n)]
    total = sum(A)
    for i in range(n):
        B[i] = total - A[i]
    return B

Lo interesante de esta solución, además de que nos dará un polinomio diferente, es que definitivamente no podemos asumir que cada línea tiene un costo constante ya que al realizar el análisis línea por línea notaremos que en esta versión más "Pythonic" (paytónica 😝, o como se diga) la línea 3 (definición por list comprehension) y la línea 4  (la función sum) suceden \(n\) veces en cada una (revisa los links). Habiendo hecho la anterior aclaración, el análisis línea por línea nos arroja el siguiente chorizo (función):

$$ T(n) = c_2 + c_3 \cdot n + c_4 \cdot n + c_5 \cdot n + c_6 \cdot n + c_7$$

Que también se puede reducir a:

$$ T(n) = n(c_3 + c_4 + c_5 + c_6) + (c_2 + c_7) $$

Y finalmente simplificar a:

$$ T(n) = an + b $$

La cuál es una función lineal y tal vez ya te estés imaginando por dónde va todo esto del análisis de algoritmos.

Por último, de la misma manera en la que lo hicimos con las constantes y finalmente con los coeficientes \(a\), \(b\), \(c, ...\), podemos simplificar todavía más nuestras funciones. Ésta vez las simplificaremos usando la tasa de crecimiento (rate of growth) de la función, es decir, usando el grado del polinomio, de tal forma que podemos decir que nuestro primer algoritmo array_difference() tiene una función con una tasa de crecimiento cuadrática (\(n^2\)) mientras que nuestro segundo algoritmo tiene una tasa de crecimiento lineal (\(n\)). Esto es posible ya que para entradas suficientemente grandes los demás términos del polinomio se vuelve insignificantes. La siguiente gráfica lo ejemplifica mejor:

Source: https://www.slideshare.net/sumitbardhan/algorithm-analysis

Utilizar la tasa de crecimiento para clasificar algoritmos facilita mucho las comparaciones ya que ahora resulta bastante obvio saber qué algoritmo es más eficiente conforme \(n\) se acerca a valores más y más grandes.

Antes de continuar con la notación asintótica (asymptotic notation) quiero recordar que el análisis de algorimos se trata acerca de predecir los recursos que un algoritmo ocupará durante su ejecución para cualquier entrada de tamaño \(n\), pero hasta ahora únicamente hemos hablado acerca de tiempo. ¿Qué pasaría con el problema anterior, y las soluciones dadas, en términos de memoria si regresar un nuevo arreglo no fuera requisito?, es decir, si pudieramos mutar el arreglo que recibimos de manera que se sigan cumpliendo las condiciones del problema. En ese caso:

  1. La solución cuadrática (array_difference) no podría sufrir ninguna optimización en espacio ya que si modificamos el arreglo \(A\), afectaríamos el resultado de los elementos en cada iteración. Dicho lo anterior y sabiendo que siempre tenemos que crear un nuevo arreglo de tamaño \(n\) para almacenar los datos, podemos concluir que nuestra solución crece de manera lineal (\(n\)) en espacio respecto al tamaño de la entrada. En resumen, la complejidad del algoritmo es del orden \(n^2\) en tiempo y \(n\) en espacio (memoria).
  2. La solución lineal (efficient_array_difference) sí puede sufir una optimización en espacio ya que una vez que calculamos la suma total del arreglo no necesitamos los valores inicales de cada elemento por lo que podemos ahorrarnos la creación del arreglo \(B\). Cuando la cantidad de recursos utilizados no depende del tamaño de la entrada se dice que entonces su tasa de crecimiento es constante ya que no importa si el problema crece a \(10^{10}\) o \(10^{100}\), el uso de los recursos no aumenta. En nuestro caso, éste algoritmo pasaría de tener una tasa de crecimiento lineal \(n\) a una constante en espacio y se mantendría en una lineal (\(n\)) en tiempo. La solución de dicha optimización luciría así:
def efficient_array_difference(A):
    total = sum(A)
    for i in range(len(A)):
        A[i] = total - A[i]
    return A

Notación asintótica

Hasta este punto hemos detallado algoritmos de arriba a abajo, línea por línea y los hemos llevado hasta categorías generales que los clasifican basados en su grado polinómico, pero jamás nos paramos a preguntar si nuestro algoritmo se comportará de la misma manera todas las veces. Resulta que para nuestros algoritmos particulares no existe un "peor de los casos" ni un "mejor de los casos" pero definitivamente es algo común entre los algoritmos, por ejemplo, y regresando al tema de ordenamiento de arreglos, algoritmos como Quicksort alcanzan órdenes cuadráticos en el peor de los casos, pero se sabe que en el promedio de los casos su orden suelen estar dentro de \(n \log{n} \) (lo veremos más adelante), también se sabe que jamás va a tener un mejor rendimiento que ese.

Encontrar el mejor de los casos, el peor y el promedio es algo necesario para el análisis de cualquier algoritmo ya que necesitamos tener certeza sobre las fronteras de nuestra solución (tanto inferiores como superiores) si queremos compararlos con otros. Por otro lado, se dice que cuando nos enfocamos en analizar las fronteras de nuestro algoritmo para números suficientemente largos tales que los términos de menor grado del polinomio resultan insignificantes, estamos interesados en estudiar la eficiencia asintótica del mismo.

Nosotros usaremos la notación asintótica para explicar los límites de la eficiencia (complejidad) de un algoritmo pero realmente éste no es su uso directo. La notación asintótica es usada en general para cualquier tipo de función matemática. En nuestro caso es útil ya que para cada una de nuestras soluciones fuimos capaces de proveer una función de costo del tipo \(T(n)\).

En resumen, la notación asintótica describe los límites de una función cuando sus parámetros tienden a un valor particular o al infinito.

Regresando a los escenarios de un algoritmo, estamos interesados en tres casos particulares:

  1. El peor el de los casos: El límite superior. Denotado como \(O\) (big-O).
  2. El mejor de los casos: El límite inferior. Denotado como \(\Omega\) (omega).
  3. El rango: Incluye ambos límites, el inferior y el superior. Denotado como \(\Theta\) (theta).

Por lo que si alguna vez encuentras en la literatura algo como "la complejidad de tal algoritmo es \(O(2^n)\)", puedes estar seguro de que se refiere al peor de los casos.  Adicionalmente, si encuentras algo como "la complejidad de tal algoritmo es \(\Theta(\log{n})\)", significa que dicho algoritmo nunca tendrá una complejidad mejor a \(\Omega(\log{n})\) ni peor a \(O(\log{n})\).

Formalmente las notaciones anteriores están definidas de la siguiente manera:

Notación-\(O\):

$$ \text{Dada una función } g(n), \ O(g(n)) \text{ es el conjunto de funciones tal que: } $$

$$O(g(n)) = \{ f(n) \  | \text{ existen constantes positivas }c, n_0 \text{ tal que:} $$

$$0 \leq f(n) \leq cg(n) \ \  \forall n\geq n_0 \}$$

O gráficamente:

Lo cual ciertamente implica que si una función tiene una complejidad \(O(n)\) también tendrá una complejidad \(O(n^2)\), como también tendrá complejidad \(O(n^3)\), etc. En esta oración es muy importante mencionar algunas cosas:

  1. Aunque lo anterior sea cierto, es decir, \(O(n) \subset O(n^2) \subset O(n^3)...\), por convención se utiliza la frontera más cercana. Por ejemplo: en la solución efficient_array_difference del problema anterior se cumple por definición que la complejidad es \(O(n^4 )\) pero realmente siempre se va a decir que la complejidad de efficient_array_difference es \(O(n)\) y consecuentemente la complejidad de array_difference es \(O(n^2)\).
  2. Si bien es cierto que la notación asintótica declara un conjunto de funciones y decir que un algoritmo tiene cierta complejidad \(f(n)\) significa realmente que \(f(n) \in O(g(n))\), la notación suele ser abusada y en su lugar se dice que \(f(n) = O(g(n))\).
  3. Los términos constantes de las funciones siempre son eliminados ya que la definición ya los toma en cuenta, por ejemplo, en lugar de escribir \(O(3n^2)\) se escribe \(O(n^2)\), de la misma manera, usamos \(O(\log{n})\) en lugar de \(O(\log_2{n})\).
  4. Por último, si la complejidad es constante, es decir, no depende del tamaño de \(n\), se utiliza \(O(1)\).
  5. Lo anterior será cierto para las siguientes notaciones asintóticas.

Notación-\(\Omega\):

$$ \text{Dada una función } g(n), \ \Omega(g(n)) \text{ es el conjunto de funciones tal que: } $$

$$\Omega(g(n)) = \{ f(n) \  | \text{ existen constantes positivas }c, n_0 \text{ tal que:} $$

$$0 \leq cg(n) \leq f(n) \ \  \forall n\geq n_0 \}$$

O gráficamente:

Notación-\(\Theta\):

$$ \text{Dada una función } g(n), \ \Theta(g(n)) \text{ es el conjunto de funciones tal que: } $$

$$\Omega(g(n)) = \{ f(n) \  | \text{ existen constantes positivas }c_1, c_2, n_0 \text{ tal que:} $$

$$0 \leq c_1g(n) \leq f(n) \leq c_2g(n)\forall n\geq n_0 \}$$

Aunque existen otras notaciones asintóticas además \(O\), \(\Theta\) y \(\Omega\) como la \(o\) y la \(\omega\) la notación de Big-O (\(O\)-notation) suele ser la más utilizada. A continuación listo algunas de las complejidades más comunes en Ciencias de la Computación ordenadas desde la más eficiente hasta la menos eficiente:

  • \(O(1)\)
  • \(O(\log{n})\)
  • \(O(n)\)
  • \(O(n \log{n})\)
  • \(O(n^2)\)
  • \(O(n^3)\)
  • \(O(2^n)\)
  • \(O(n!)\)

Conclusión

La complejidad computacional no sólo es relevante en el contexto de la clasificación de algoritmos, también juega un rol importantísimo en la clasificación de problemas. Es gracias a ella que podemos argumentar que no es lo mismo buscar un elemento en una base de datos que resolver un juego de ajedrez. De hecho, es de la complejidad computacional que se deriva uno de los problemas más importantes de las Ciencias de la Computación, y uno de los problemas del milenio: P vs NP (del cual trataré de escribir en otra ocasión). Y por si eso no fuera suficiente, uno de los factores más importantes de la criptografía moderna recae sobre el hecho de que los problemas computacionales involucrados en ella tienen complejidades altísimas, por ejemplo: la factorización de primos o generar todas las combinaciones posibles de 256/512/1024/etc bits. Existen problemas que incluso contando con todo el tiempo del universo (desde su nacimiento, hasta su muerte) no podrían ser resultos.

Por otro lado, a pesar de que la notación asintótica ya nos da una idea acerca del tiempo que toma resolver un problema, no es raro encontrar tablas que muestren los valores de cada complejidad conforme \(n\) crece, aquí hay un ejemplo:

Imagina una computadora capaz de realizar \(10^9\) operaciones primitivas por segundo. ¿Recuerdas el problema anterior? Bueno, para una lista de 1 millón de elementos (\(n = 10^6\)) array_difference, con una complejidad de \(O(n^2)\), tomaría al rededor de 16 minutos, mientras que efficciente_array_difference, con una complejidad de \(O(n)\), tomaría 1 milisegundo. O peor aún, si la longitud de la lista fuera de 1 billón de elementos (\(n = 10^9\)): array_difference tomaría más de 31 años mientras que efficciente_array_difference sólo tomaría 1 segundo. La complejidad computacional es importante.

Comentarios

No olvides revisar la complejidad computacional detrás de las sentencias mágicas del lenguaje de programación que estés utilizando, nunca sabes cuándo puede haber un \(O(n)\) detrás.

Como último comentario, y particularmente si vienes de un background de ingeniería de software, la generalización no siempre es lo que buscas ya que en ocasiones la optimización puede suceder al nivel de las constantes. Un ejemplo que nos sucedió en una empresa de desarrollo de software es: En algún punto tuvimos un cliente al que se le hizo fácil utilizar una de estas plataformas backend as a service tipo Firebase para persistir toda la información de su negocio, lo cual significaba que los datos únicamente podían ser accedidos a través de la red usando un API REST 🤦‍♂️, y al estar diseñando una funcionalidad que generaba facturas para compras "masivas" nos dimos cuenta que, incluso haciendo bulk requests y persistiendo cosas en caché, teníamos una función de costo del tipo \(T(n) = c(6n + 3)\) donde \(c\) era el tiempo en milisegundos que tardaba "Firebase" en responder a una petición HTTP y \(n\) los elementos que se estaban agregando a la factura. Para tiempos de respuesta extreamadamente optimistas (\(c=120ms\)) y \(n = 100\) (por cierto, por debajo de la demanda esperada, \(n\geq 150\)) un cliente tenía que esperar al rededor de 20 minutos para obtener su factura, cosa que con una base de datos de verdad tomaba menos de 1 segundo para \(n \leq 1000\). Haber generalizado \(T(n)\) en \(O(T(n))\) nos hubiera dado una expectativa bastante alejada de la realidad ya que no estábamos trabajando con números lo suficientemente grandes. En ese caso, bajar la constante que multiplicaba a \(n\) podía hacer la diferencia entre esperar 20 minutos (\(6\)) y 3 minutos (\(1\)), además ahorrarle algunos miles de USD al cliente.

En el siguiente post escribiré acerca de arreglos y la complejidad computacional detrás de sus operaciones más comunes. Prometo que trataré de contener mi lenguaje coloquial/mexicano lo más posible (nocierto 😝). También habrán menos formalidades matemáticas.

Recursos