Introducción a Big O Notation

¿Sabes cuál es la complejidad del algoritmo de búsqueda binaria?

Bien, si dudaste, veamos de cerca la respuesta…

Cuando hablamos de rendimiento y optimización, es importante tener una métrica para determinar qué tan bueno es un algoritmo en algunos casos y qué tan malo puede ser para otros. Para esto existe Big O notation.

Big O notation nos permite dar una nomenclatura o simbología a la complejidad de los algoritmos. Pongamos como ejemplo un algoritmo de búsqueda, del cual queremos saber su velocidad. Es necesario tener en cuenta que no podemos hablar de tiempo, ya que eso depende del hardware en el que se ejecute: en una MacBook, el mismo algoritmo funcionará más rápido que en un smartphone de gama baja.

Otro factor a tener en mente es que la mayoría de los algoritmos cambian su rendimiento dependiendo la cantidad de datos que va a procesar. Es decir, algunos algoritmos de búsqueda lo hacen bien cuando el tamaño del input es pequeño, pero pierden efectividad si incrementa y viceversa. Tenemos que considerar el tamaño de los datos, así como el análisis de su posible crecimiento o el peor escenario.

Big O notation es utilizado en ciencias computacionales para describir el rendimiento complejidad de un algoritmo. Generalmente describe el peor escenario, es decir, el máximo tiempo en la mayor cantidad de repeticiones que el algoritmo tiene que ejecutar.

Algunos ejemplos populares de expresiones Big O notation son:

O(1) — notación constante
Esta expresión indica tiempo constante, lo que significa que el algoritmo se ejecutará con el mismo rendimiento sin importar el tamaño del input. Esto no quiere decir que sólo tendrá un input, más bien no se verá afectado por la cantidad de datos que estemos manejando.

Ejemplo:

function findByIndex(food, index) {
  return food[index];
}
var food = ['🍿', '🍔', '🍩', '🍗'];
console.log(findByIndex(food, 2));   🍩

O(n) — notación lineal
Esta es la expresión de crecimiento lineal, la complejidad del algoritmo aumenta de manera proporcional al tamaño del input.

Ejemplo:

function selectedFood(food) {
  food.forEach(objectFood => 
       console.log(objectFood, objectFood)
  );
}
const food = ['🍿', '🍔', '🍩', '🍗'];
selectedFood(food); // 🍿🍿​​​​​ 🍔🍔​​​​​ ​​​​🍩🍩​​​​​ ​​​​​🍗🍗​​​​​

O(n2) — notación cuadrática
Indica que el crecimiento en complejidad es proporcional al cuadrado del tamaño del input. Estos algoritmos suelen ser los menos eficientes, no se recomiendan para datos grandes y normalmente se dan cuando usamos ciclos for o iteraciones anidadas; es decir, si dentro de cada iteración de un arreglo lo vuelves a iterar, tendrás un algoritmo de complejidad cuadrada. Estos pueden llegar a complejidades cúbicas o factoriales.

Ejemplo:

function bubbleSort(array){
  array = array.slice();
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}
var array = [ 4, 3, 2, 1];
console.log(bubbleSort(array)); // [ 1, 2, 3, 4]

O(log n) — notación logarítmica
Indica que el tiempo aumenta linealmente, mientras que n sube exponencialmente. Entonces, si se tarda 1 segundo en calcular 10 elementos, se necesitarán 2 para 100, 3 para 1000 y así sucesivamente.

Ejemplo:

function binarySearch(array, element, start = 0, end = (array.length - 1)) {
  if (end < start) return -1;
  var middle = Math.floor((start + end) / 2);
  return element === array[middle]
    ? middle
    : element < array[middle]
      ? binarySearch(array, element, start, middle - 1)
      : binarySearch(array, element, middle + 1, end);
}
var unsortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log("Index of 2: ", binarySearch(unsortedArray, 2));    // Index of 2: 1
console.log("22 not found: ", binarySearch(unsortedArray, 22)); // 22 not found: -1

Bien, teniendo en cuenta estas expresiones, quiero mostrarles un resumen visual de Aditya Y. Bhargav en su libro grokking algorthims, que muestra una comparativa genial de tiempo y tamaño de ejecución de lo que acabamos de ver:

En conclusión, ahora ya sabes que cuando te pregunten “¿cuál es la complejidad de un algoritmo?” esperan que mediante una expresión indiques cómo el tamaño afecta al rendimiento del mismo.

Nos leemos luego.