Big O - Intro al Análisis de Complejidad Algorítmica

No sé ustedes, pero a mí me gusta que todo lo que yo corra en mi computadora funcione lo más rápido posible. Es más, hasta cierto punto, estoy dispuesto a sacrificar funcionalidades y sacrificar gráficos bonitos con tal de poder hacer lo que quiera más rápido. ¿Uso ese tiempo aprovechado de forma productiva? No, usualmente lo ocupo en dormir, ver tele, o comprar juegos que no voy a jugar nunca.

Ahora, por más que yo sepa que soy una personita especial, está probado que no soy el único que no sabe lo que quiere, pero lo quiere YA. Podría ponerme a citar estudios de pérdidas de clientes por el retraso de tiempos de respuesta en sitios web o como, en el ambiente de videojuegos, más framerate en un FPS competitivo se correlaciona con una mayor precisión y éxito.

… O simplemente podría decir que excepto en criptografía, en cosas referidas a la computación, si es más rápido, va a ser mejor.

Bueno, pero… como arranco?

Arranquemos por entender que es Big O

Matemáticamente, Big O (también llamada “Notación O grande” o " Curva Superior Asintótica “) se describe como una función que representa el crecimiento de alguna función en análisis, cuando los argumentos de esta última tienden al infinito (crecen mucho).

En Computación, Big O se usa para describir la performance esperada de un algoritmo, al establecer una relación entre la cantidad de datos de entrada, con la cantidad de operaciones requeridas para obtener un resultado. O, en otras palabras, establece como crece la cantidad de operaciones que realiza una función respecto a la cantidad de datos de entrada que reciba.

La idea es enfocarnos en el peor caso posible de ejecución de un algoritmo, en términos del tiempo que tarde en terminar de ejecutarse y el espacio requerido en memoria o en disco, para así comparar de forma objetiva una solución con otras.

Okay, y como lo calculo?

La idea básica es sumar operaciones en bloque, hasta llegar al total de una función, pero hay un par de reglas extras a considerar.

Empecemos con un ejemplo fácil:

// Esta funcion compara el parametro con 0, nada mas
function isBiggerThanZero(a) { // tenemos un valor de entrada...
    if (a > 0) { // y una sola operacion
        return true
    } 
    return false
}

Acá tenemos un valor de entrada, y una operación, tanto en el mejor como en el peor caso. El Big O de esta función es una constante, 1. Expresado en fórmula se escribe O(1).

Ahora analicemos algo un poco más complejo:

// Esta función recibe un array y busca un elemento en el mismo
function linearSearchIndex(array, value) {
  for (let index= 0; index< array.length; index++) {	
   // Al principio se define una única vez el puntero "index", 
   // y por cada elemento recorrido del vector hace dos cosas: 
   // verifica si el puntero es menor al limite y suma 1 al puntero, 
   // por lo que podríamos decir que acá tenemos O(2N + 1)

    // A continuación, otra comparación por cada valor del vector: O(N)
    if (array[index] === value) return index;  // happy ending😄
  }
  return -1;  // sad ending 😢     
};

Acá la cosa se pone interesante: tenemos una función en la que la cantidad de operaciones depende de la cantidad de valores de entrada. Es decir que, si tenemos N valores de entrada, es posible que tengamos que comparar N valores.

Sumando los Big O de cada parte de la función podríamos intuir que el Big O total de esta función es O(3N + 1). Pero no, esta función tiene un O(N)… por qué?.

Por dos reglas prácticas:

• Al escribir la notación, se desprecian las constantes: es decir que un O(2N+1) se escribe como O(N). Cabe mencionar que esto se hace para facilitar el análisis, en la práctica las constantes también influyen en la velocidad de un algoritmo, pero no tanto como la forma de la curva.

• Y segundo, y más importante, al definir que valores poner, se toma el valor con crecimiento más alto: es decir que si tenemos una función con alguna parte con O(N), otra con O(N2)y otra con O(1), el O(1) se descarta.

  O sea que a la hora de analizar un ciclo for o while, ignoramos las operaciones auxiliares (como establecer el valor inicial del índice, o comparar el índice con el tamaño del vector) y decimos simplemente que la complejidad es N, porque depende de los N valores de entrada. Capisci?

Así, lo que esperaban que fuese O(3N + 1) se convierte en O(3N) después de aplicar la primera regla, y en O(N) luego de aplicar la segunda.

¿Pero, y esto de donde viene?

Los tipos de complejidad más comunes que se van a encontrar son los siguientes (en orden de menor a mayor velocidad de crecimiento):

Quienes se acuerden de algo de matemática, van a notar que esto se corresponde con algunos tipos de funciones. ¡Es justamente eso!

Acá está la representación visual de curvas con estos órdenes de magnitud.

¿Notan como las curvan van creciendo más rápido o más lento?

Pero… para qué me sirve esto?

Primero, fuera de todo ámbito práctico, esto les permite definir si una solución u otra es objetivamente más rápida. Al resolver un problema, y superados pequeños obstáculos como “esta función no me explota la computadora”, y “esta función retorna los valores correctos”, llega la parte divertida que es optimizar todo lo posible la solución para que ande Todo rápido, Todo bonito™.

Veamos esto con otro ejemplo, partiendo desde el caso anterior, y construyendo un mejor algoritmo de búsqueda. Si asumimos que tenemos una lista ordenada de ítems, podemos utilizar un algoritmo de búsqueda binaria:

Este algoritmo lo que hace es ir dividiendo el vector en estudio, de una forma que termina siendo mucho mas eficiente que ir elemento por elemento como hace la búsqueda lineal. ¡Pueden verlo implementado en este Gist!

Y acá pueden ver un GIF genial que compara las dos estrategias de búsqueda mostradas hasta ahora:

El Big O de este algoritmo es O(Log(N)). ¿Cómo lo calculé? Bueno, si hacemos un árbol con los caminos de búsqueda del algoritmo en algún caso particular (ponele, 15 elementos), podemos ver que la máxima cantidad de operaciones en el peor caso es 4, que s igual al Log2(15 + 1), es decir que para una entrada de tamaño N, el algoritmo realiza Log2(N + 1) operaciones.

Como ya expliqué antes, por convención y practicidad descartamos las constantes, por lo que la complejidad del algoritmo es de O(Log(N))

¿Asusta? No te va a tocar hacer este análisis matemático cada vez, no te preocupes. La realidad es que la gran mayoría de las veces vas a saber que algoritmo estás aplicando, para estos algoritmos más complicados de analizar, y podés googlear la complejidad computacional del que estés implementando.

Comparando Algoritmos!

Bien, ya sabemos entonces que el Big O del algoritmo de búsqueda binaria es O(Log(N)), mientras que el de búsqueda lineal es O(N). Puede que consideren que no haya tanta diferencia entre una y otra, teniendo en cuenta que en la tabla de tipos de complejidad, O(Log(N)) está justo por encima de O(N) en términos de complejidad.

Hice varias pruebas y estos son los resultados:

Y eso que en este ejemplo lo único que hacemos es buscar un valor en un vector en memoria. ¡Un retardo de este tipo, por ejemplo, puede ser la diferencia que haga que una petición a un servidor, no sea respondida porque se agote el tiempo de espera!

Y esto es una búsqueda de números enteros simples, en mi computadora que es bastante rápida… imaginen que tuvieran que… no sé, ¿calcular la probabilidad de que cada uno de los elementos sea el correcto?, ¿o que tengan que obtener la información con un volumen de datos más considerable?, ¿o si tienen que buscar una palabra en un texto largo?, ¿O si este procesamiento se tuviese que hacer en el celular lento de un cliente?.

Esta puede ser la diferencia entre un sistema lento y un sistema rápido. La diferencia entre una aplicación ágil, y una app que los usuarios cierran porque piensan que no responde.

Optimizar Algoritmos es genial!

Si tenemos que buscar en un vector de 10 elementos, optimizar la búsqueda no tiene importancia, pero cuando se maneja un volumen de datos más importante, o se hacen operaciones más complejas en cada elemento, la diferencia puede ser impresionante.

Algo relevante a mencionar es que la optimización de algoritmos (o al menos entender que es Big O) se suele pedir como parte de entrevistas de trabajo técnicas de algunas empresas para puestos avanzados, y fuera de eso, resolver este tipo de desafíos nos abre la cabeza y nos ayuda a entender cómo funciona un lenguaje de programación.

¡Si se quedaron con ganas de más, léanse este artículo de freeCodeCamp que está bueno!