Complejidad Algorítmica y Notación Big O

En este artículo vamos a entender que es un algoritmo y como usar la notación Big O para poder analizar la complejidad temporal del mismo. Esto nos va a ayudar a entender el uso de recursos de cómputo y la eficiencia en velocidad dentro de nuestros programas, además suele ser una forma de evaluar a developers o ingenieros de software.

¿Qué es un algoritmo?

Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. O sea, una serie de pasos a seguir para completar una tarea.

¿Qué hace bueno a un algoritmo?

1. Resuelve un problema: Este es el objetivo principal del algoritmo, fue diseñado para eso. Si no cumple el objetivo, no sirve para nada.

2. Debe ser comprensible: El mejor algoritmo del mundo no te va a servir si es demasiado complicado de implementar.

3. Hacerlo eficientemente: No sólo queremos tener la respuesta perfecta (o la más cercana), si no que también queremos que lo haga usando la menor cantidad de recursos posibles.

De hecho estas dos condiciones a veces van en contra: encontrar la solución perfecta atenta contra el tiempo que va a tardar, y hacerlo rápido atenta contra la precisión de la respuesta. Vamos a tener que saber qué usamos en cada caso.

¿Cómo medimos la eficienta del un algoritmo?

Lo más fácil y rápido de hacer es contar cuanto tiempo le lleva al algoritmo encontrar la respuesta que buscamos. Pero eso nos diria la eficiencia de ese algoritmo sólamente para la computadora que lo corrió, con los datos que tenia y en el lenguaje que se haya implementado, no? Entonces como hacemos para comparar la eficiencia de distintos algoritmos? Para eso se hace un análisis conocido como Asymptotic Analysis, vamos a entender el concepto mas adelante.

Complejidad de un algoritmo

En general nos interesa conocer qué tan complejos son los algoritmos, o en realidad, lo contrario: que tan eficiente es un algoritmo.
Hay muchos aspectos que afectan la complejidad de un algoritmo:

• Tiempo
• Espacio
• Otros recursos:
  • Red
  • Gráficos
  • Hardware (Impresoras, Cpus, Sensores, etc...)

La mas común, y en la que nos vamos a concentrar mayormento es la complejidad de tiempo, es decir la velocidad algoritmo, o cuanto tarda en correr. Otro tipo de complejidad importante es el espacio, o sea la cantidad de memoria (RAM o disco) que necesitamos para poder corer un algoritmo. De hecho, a veces cambiamos la complejidad de tiempo por la de memoria, un algoritmo va a consumir más espacio en memoria, pero va a correr más rápido.
Otros algoritmos pueden requerir otros recursos, como por ejemplo algún algoritmo que se ejecute distribuido por la red, en ese caso el algoritmo se verá limitado por la velocidad y tamaño de la misma. Otro usarán otros tipos de recursos.

Circunstancias

¿Cómo sabemos cuando un auto es más rápido que otro? 

Bueno, si los ponemos en un tramo igual, y tomamos nuestros relojes para medir cuánto tardan, podremos ver que uno llega más rápido que otro a la meta. Que un auto tarda menos que otro. Tal vez unos 10, o 20, o 30 minutos.

Entonces, medir es clave para determinar el mejor. Pero la Complejidad en sí no trata de si un auto llega 10, o 20 o 30 minutos más rápido a la meta. Si no del ritmo con el que aumenta.

La teoría de la complejidad estudia el consumo de recursos (tiempo, espacio) que un algoritmo ocupa. la complejidad algorítmica no se fija en el tiempo de ejecución del algoritmo (segundos, minutos, horas, etc), se fija en el ritmo y que tan eficiente puede ser un algoritmo en base al problema que está resolviendo.

¿Qué es este ritmo con el que aumentan los datos? ( EN CRIOLLO )

Supongamos que tenemos dos algoritmos para ordenar números.
Entonces tenemos un algoritmo A, medimos cuánto se tardará en ordenar diez, veinte y treinta números, y resulta vamos a requerir 10 segundos, 20 segundos y 40 segundos. Luego viene un algoritmo B, medimos otra vez, y requerirá 10 segundos, 10 segundos y 10 segundos. El aumento de tiempo es distinto en ambos. Entonces tenemos un algoritmo A que cada vez se demora más en calcular el ordenamiento (multiplicando cada vez por 2), y un algoritmo B que demora el mismo tiempo (multiplicando cada vez por 1). Este factor es el ritmo:

Cota superior asintótica ( Big O Notation )

Vamos a usar una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.

Definicion formal:

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor x0, f(x) no sobrepasa a cg(x). Quiere decir que la función f es inferior a g a partir de un valor dado salvo por un factor constante.

Puede parecer un poco dificil pero en la practica es mucho más simple que eso. La notación Big O intenta analizar la complejidad de los algoritmos según crece el número de entradas ( n ) que tiene que analizar, en general es el tamaño del dataset que usa como entrada. Y lo que busca es una función que crezca de una forma con respecto a n tal que nuestro algoritmo nunca crezca más rápido que esa función, aunque si puede crecer más lento. Básicamente, estamos buscando algo para poder decir: mirá este algoritmo nunca va a tardar más que esto, capaz tarda menos, pero más no.

Lo que hace a Big-O tan importante es que se destaca en concentrarse en el caso peor de tu algoritmo. En el tope superior de nuestras mediciones. Si nuestro algoritmo empezó con unas mediciones muy buenas, pero de pronto creció mucho en el consumo de un recurso. Big-O tomará en cuenta esto último para determinar qué crecimiento le pertenece.

Buscamos descubrir una función (Constante, Lineal, Polinomial, Logarítmica, Exponencial) la cual sea mayor o igual que la complejidad de un algoritmo

Clases de Big-O

Vamos a intentar crear un algoritmo en el que su ritmo de crecimiento no sea muy elevado.

Comparación Gráfica

Arriba podemos ver una comparación gráfica de las distintas complejidades de los algoritmos.

Si tuvieramos una computadora capaz de ejecutar 1.000.000 instrucciones por segundo, veamos cuanto tiempo tardarían algoritmos de distinta complejidad en terminar de correr con un N de entrada de 1000.

Calculo de Notación Big-O en complejidad temporal

Vamos a ver Las reglas en el codigo para Big-O en calculo de complejida temporal

let bar = 'test' // O(1)

if(){} // O(1)

for(){} // O(n)

while(){} // O(n)

for(){ for(){} } // O(n^2)

Simplificar la notación

Simplificar la notación de la complejidad se lleva a la expresión del elemento con mayor grado.

¿Por qué nos quedamos con el grado mayor al simplificar Big-O?

En Big-O queremos comprender qué tanto recurso (como tiempo o espacio) nos gasta un algoritmo cuándo aumentamos los datos. Y cada grado aumenta a un ritmo totalmente distinto.

Por ejemplo n crece más que 1000:

No es necesario quedarnos con los grados pequeños: Podemos simplificar y quedarnos con lo importante.

Ahora lo podemos poner en práctica analizando los siguientes programas:

// Complejidad Temporal -> O( n + 3 ) -> O(n)

function linearSearch(arreglo, clave) {

  for (let indice = 0; indice < arreglo.length; indice++) { // O(n)

    if (arreglo[indice] === clave) { // O(1)

      return indice; // O(1)

    }

  }

  return -1; // O(1)

}

// Complejidad Temporal -> O( 1 + n * n + 1 + 1 + 1 + 1 + 1 ) -> O(n^2 +6) -> O(n^2)

function bubbleSort(arreglo) {

  let longitud = arreglo.length; // O(1)

  for (let i = 0; i < longitud; i++) { // O(n)

    for (let j = 0; j < longitud; j++) { // O(n)

      if (arreglo[j] > arreglo[j + 1]) { // O(1)

        let temporal = arreglo[j]; // O(1)

        arreglo[j] = arreglo[j + 1]; // O(1)

        arreglo[j + 1] = temporal; // O(1)

      }

    }

  }

  return arreglo; // O(1)

}

//Complejidad Temporal -> O( n^2 )

function selectionSort(arreglo) {

  let longitud = arreglo.length; // O(1)

for (let i = 0; i < longitud; i++) { // O(n)

    let minimo = i; // O(1)

    for (let j = i + 1; j < longitud; j++) { // O(n)

      if (arreglo[j] < arreglo[minimo]) { // O(1)

        minimo = j; // O(1)

      }

    }

    if (minimo != i) { // O(1)

      let temporal = arreglo[i]; // O(1)

      arreglo[i] = arreglo[minimo]; // O(1)

      arreglo[minimo] = temporal; // O(1)

    }

  }

  return arreglo; // O(1)

}

Notas finales sobre algoritmos

Hasta ahora sabes que un algoritmo con O(1) es mejor que uno con O(n). Pero, ¿Y si ese algoritmo con O(1) se ejecuta en 1000 horas?

La complejidad algorítmica es importante, pero dónde se ejecuta tu algoritmo determina qué tan importante es.

Cuando la Complejidad Algorítmica deja de ser relevante, es donde debemos mejorar nuestro algoritmo para alcanzar nuestro objetivo de eficiencia.

Tal vez tengamos el mejor algoritmo jamás visto, pero si lo ejecutamos en una computadora de hace 20 años con Intel Celeron no podemos esperar mucha rapidez

¿Solo hay Big-O para tiempo?

No, también se puede aplicar al cálculo del espacio, por ejemplo en JavaScript es más relevante apuntar al tiempo, que al espacio. Porque en el código JavaScript usualmente no corre en dispositivos con memoria muy limitada a diferencia de dispositivos embebidos donde el espacio que tiene en la memoria es más reducido y por lo tanto más relevante para nuestro análisis.

Esto no significa que no haya casos particulares, o que el espacio siempre sea menos importante que el tiempo, sólo es el ambiente del software con JavaScript. la complejidad es el estudio de los recursos que utilizan los algoritmos. Estos recursos pueden ser cualquier concepto de hardware y software. Como acceso a la memoria, comparaciones de condiciones, o lo que se necesite limitar.

finalmente

Esta lectura fue un resumen a grandes rasgos sobre la complejidad algorítmica. Si te interesa profundizar sobre el tema y su aplicación en estructuras de datos te recomiendo los siguientes recursos gratuitos ofrecidos por Freecodecamp:
Data Structures Easy to Advanced Course
Big O Notation - Full Course