Original article: Big O Cheat Sheet – Time Complexity Chart

Un algoritmo es un conjunto de instrucciones bien definidas para resolver un problema específico. Puedes resolver estos problemas de varias maneras.

Esto significa que el método que uses para llegar a la misma solución puede diferir del mío, pero ambos deberíamos obtener el mismo resultado.

Debido a que hay varias maneras de resolver un problema, debe haber una manera de evaluar estas soluciones o algoritmos en términos de rendimiento y eficiencia (el tiempo que tardará tu algoritmo en ejecutarse y la cantidad total de memoria que consumirá).

Esto es fundamental para que los programadores se aseguren de que sus aplicaciones se ejecuten correctamente y les ayuden a escribir código limpio.

Aquí es donde la notación Big O entra en escena. La notación Big O es una métrica para determinar la eficiencia de un algoritmo. Le permite estimar cuanto tiempo se ejecutará su código en diferentes conjuntos de entradas y medir la eficacia con la que su código escala a medida que aumenta el tamaño de su entrada.

¿Qué es Big O?

Big O, también conocida como Notación Big O, representa la complejidad del peor de los casos de un algoritmo. Utiliza términos algebraicos para describir la complejidad de un algoritmo.

Big O define el tiempo de ejecución necesario para ejecutar un algoritmo identificando como cambiará el rendimiento de su algoritmo a medida que crece el tamaño de la entrada. Pero no le dice que tan rápido es el tiempo de ejecución de su algoritmo.

La notación Big O mide la eficiencia y el rendimiento de su algoritmo usando la complejidad del tiempo y el espacio.

¿Qué es la complejidad del tiempo y el espacio?

Un factor subyacente importante que afecta el rendimiento y la eficiencia de su programa es el hardware, el sistema operativo y la CPU que utiliza.

Pero no se tiene en cuenta esto cuando se analiza el rendimiento de un algoritmo. En cambio, lo que importa es la complejidad temporal y espacial en función del tamaño de la entrada.

La complejidad temporal de un algoritmo especifica cuanto tiempo llevará ejecutar un algoritmo en función de su tamaño de entrada. De manera similar, la complejidad espacial de un algoritmo especifica la cantidad total de espacio o memoria necesaria para ejecutar un algoritmo en función del tamaño de la entrada.

Nos centraremos en a complejidad del tiempo en esta guía. Esta será una hoja de trucos detallada que le ayudará a comprender como calcular la complejidad del tiempo ara cualquier algoritmo.

¿Por qué la complejidad del tiempo esta en función del tamaño de entrada?

Para comprender perfectamente el concepto de "en función del tamaño de la entrada", imagine que tiene un algoritmo que calcula la suma de números en función de su entrada. Si su entrada es 4, sumaremos 1 + 2 + 3 + 4 y la salida será 10; si su entrada es 5, la salida será 15 (es decir, 1 + 2 + 3 + 4 +5).

const calcularSuma = (entrada) => {
  let suma = 0; // 1ra declaración 
  for (let i = 0; i <= entrada; i++) {
    suma += i; // 2da declaración
  }
  return suma; // 3ra declaración
};

Observando el código solo tenemos 3 declaraciones. Aún así, debido a que hay un bucle, la segunda declaración se ejecutará según el tamaño de la entrada, por lo que si la entrada es 4, la segunda declaración se ejecutará 4 veces, lo que significa que todo el algoritmo se ejecutará 6 veces.

En palabras sencillas, al algoritmo se ejecutará entrada + 2 veces, donde la entrada puede ser cualquier número. Esto muestra que se expresa en términos de la entrada. En otras palabras, en función del tamaño de entrada.

En notación Big O, existen 6 tipos principales de complejidades (tiempo y espacio):

  • Constante: O(1)
  • Lineal: O(n)
  • Logarítmica: O (n log n)
  • Cuadrática: O(n^2)
  • Exponencial: O(2^n)
  • Factorial: O(n!)

Antes de ver ejemplos, comprendamos el gráfico de la complejidad de tiempo Big O.

Gráfico de complejidad de Big O

El gráfico Big O es una notación asintótica que se usa para expresar la complejidad de un algoritmo o su rendimiento en función del tamaño de entrada.

Esto ayuda a los programadores a identificar y comprender completamente el peor de los casos y el tiempo de ejecución o la memoria requerida de un algoritmo.

El siguiente gráfico ilustra la complejidad Big O:

s_2D428973624E7FC84C7D69D11421DE762BEA6B6F3361231FCDCAE0425D14526F_1664885448372_Untitled.drawio-17

El grafico Big O anterior muestra que O(1), complejidad de tiempo constante, es el mejor. Esto implica que su algoritmo procesa solo una declaración sin ninguna iteración. Luego esta O(log n), que es bueno, y otros similares como vemos a continuación:

  • O(1) - Excelente/Mejor
  • O(log n) - Bueno
  • O(n) - Aceptable
  • O(n log n) - Malo
  • O(n^2), O(2^n) y O(n!) - Horrible/Peor

Ahora comprende las diversas complejidades de tiempo y puede reconocer las mejores, las buenas y las aceptables, así como las malas y las peores (evite siempre las complejidades del tiempo malo y peor).

La siguiente pregunta que me viene a la mente es como saber que algoritmo tiene que complejidad temporal, dado que este post se trata solo de una guía.

  • Cuando el cálculo no depende del tamaño de una entrada, es una complejidad de tiempo constante O(1).
  • Cuando el tamaño de entrada se reduce a la mitad, tal vez al iterar, manejar recursividad, o lo que sea, es una complejidad de tiempo logarítmica O(log n).
  • Cuando tiene un solo bucle dentro de sus algoritmo, es complejidad de tiempo lineal O(n).
  • Cuando tiene 2 bucles anidados dentro de su algoritmo, es decir, un bucle dentro de otro bucle, es una complejidad de tiempo cuadrática O(n^2).
  • Cuando la taza de crecimiento se duplica con cada iteración a la entrada, se trata de una complejidad temporal exponencial O(2^n).

Comencemos describiendo la complejidad de cada tiempo con ejemplos. Es importante tener en cuenta que usaré JavaScript en los ejemplos de esta guía, pero el lenguaje de programación no es importante siempre y cuando comprenda el concepto y la complejidad de cada tiempo.

Big O: Ejemplos de Tiempo de Complejidad

Tiempo Constante: O(1)

Cuando su algoritmo no depende del tamaño de entrada n, se dice que tiene una complejidad temporal constante con orden O(1). Esto significa que el tiempo de ejecución siempre será el mismo independientemente del tamaño de entrada.

Por ejemplo, si un algoritmo debe devolver el primer elemento de un arreglo. Incluso si el arreglo tiene 1 millón de elementos, la complejidad temporal será constante si utiliza este enfoque:

const primerElemento = (arreglo) => {
  return arreglo[0];
};

let marcadores = [12, 55, 67, 94, 22];
console.log(primerElemento(marcadores)); // 12

La función anterior requerirá un solo paso de ejecución, lo que significa que la función está en tiempo constante con una complejidad temporal O(1).

Pero como dije antes, existen varias formas de lograr una solución en programación. Otro programador podría decidir recorrer primero el arreglo antes de devolver el primer elemento:

const primerElemento = (arreglo) => {
  for (let i = 0; i < arreglo.length; i++) {
    return arreglo[0];
  }
};

let marcadores = [12, 55, 67, 94, 22];
console.log(primerElemento(marcadores)); // 12

Este es solo un ejemplo, probablemente nadie haría esto. Pero si hay un bucle, ya no es tiempo constante sino ahora tiempo lineal con complejidad temporal O(n).

Tiempo Lineal: O(n)

Se obtiene complejidad de tiempo lineal cuando el tiempo de ejecución de un algoritmo aumenta linealmente con el tamaño de la entrada. Esto significa que cuando una función tiene una iteración que itera sobre un tamaño de entrada n, se dice que tiene una complejidad temporal de orden O(n).

Por ejemplo, si un algoritmo debe devolver el factorial de cualquier número de entrada. Esto significa que si ingresa 5, debe realizar un bucle y multiplicar 1 x 2 x 3 x 4 x 5 y luego regresar 120:

const calcularFactorial = (n) => {
  let factorial = 1;
  for (let i = 2; i <= n; i++) {
    factorial = factorial * i;
  }
  return factorial;
};

console.log(calcularFactorial(5)); // 120

El hecho de que el tiempo de ejecución depende del tamaño de entrada significa que la complejidad del tiempo es lineal con orden O(n).

Tiempo Logarítmico: O(log n)

Esto es similar a la complejidad de tiempo lineal, excepto que el tiempo de ejecución no depende del tamaño de la entrada sino de la mitad del tamaño de la entrada. Cuando el tamaño de entrada disminuye en cada iteración o paso, se dice que un algoritmo tiene complejidad logarítmica.

Este método es el segundo mejor porque su programa se ejecuta con la mitad del tamaño de entrada en lugar del tamaño completo. Después de todo el tamaño de entrada disminuye en cada iteración.

Un gran ejemplo son la funciones de búsqueda binaria, que dividen el arreglo ordenado según su valor objetivo.

Por ejemplo, supongamos que utiliza un algoritmo de búsqueda binaria para encontrar el índice de un elemento determinado en un arreglo:

const busquedaBinaria = (arreglo, objetivo) => {
  let primerIndice = 0;
  let ultimoIndice = arreglo.length - 1;
  while (primerIndice <= ultimoIndice) {
    let medioIndice = Math.floor((primerIndice + ultimoIndice) / 2);

    if (array[medioIndice] === objetivo) {
      return medioIndice;
    }

    if (array[medioIndice] > objetivo) {
      ultimoIndice = medioIndice - 1;
    } else {
      primerIndice = medioIndice + 1;
    }
  }
  return -1;
};

let marcadores = [12, 22, 45, 67, 96];
console.log(busquedaBinaria(marcadores, 96));

En el código anterior, debido a que es una búsqueda binaria, primero obtiene el índice medio de su arreglo, lo compara con el valor objetivo y devuelve el índice medio si es igual. De lo contrario, debe verificar si el valor objetivo es mayor o menor que el valor medio para ajustar el primer y ultimo índice, reduciendo el tamaño de entrada a la mitad.

Debido a que en cada iteración el tamaño de la entrada se reduce a la mitad, la complejidad del tiempo es logarítmica con orden O(log n).

Tiempo Cuadrático: O(n^2)

Cuando se realiza una iteración anidada, es decir un bucle dentro de otro bucle, la complejidad del tiempo es cuadrática, lo cual es horrible.

Una manera perfecta de explicar esto sería si tuviera un arreglo con n elementos. El bucle exterior se ejecutará n veces y el bucle interior se ejecutará n veces por cada iteración del bucle exterior, lo que dará un total de n^2 impresiones. Si el arreglo tiene 10 elementos, habrán 100 impresiones (10^2).

Aquí hay un ejemplo de Jared Nielsen, donde se compara cada elemento en un arreglo para generar el índice cuando dos elementos son similares:

const elementosSimilares = (arreglo) => {
  for (let i = 0; i < arreglo.length; i++) {
    for (let j = 0; j < arreglo.length; j++) {
      if (i !== j && arreglo[i] === arreglo[j]) {
        return `Encontrado en ${i} y ${j}`;
      }
    }
  }
  return "No hay coincidencias 😞";
};

const frutas = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];
console.log(elementosSimilares(frutas)); // "Encontrado en 2 y 8"

En el ejemplo anterior, hay un bucle anidado, lo que significa que la complejidad del tiempo es cuadrática con orden O(n^2).

Tiempo Exponencial: O(2^n)

Se obtiene una complejidad temporal exponencial cuando la taza de crecimiento se duplica con cada adición a la entrada (n), a menudo iterando a través de todos los subconjuntos de los elementos de entrada. Cada vez que una unidad de entrada aumenta en 1, el número de operaciones ejecutadas se duplica.

La secuencia recursiva de Fibonacci es un buen ejemplo. Supongamos que te dan un número y quieres encontrar el n-simo elemento de la secuencia de Fibonacci

La secuencia de Fibonacci es una secuencia matemática en la que cada número es la suma de los dos números anteriores, donde 0 y 1 son los dos primeros números. El tercer número es la secuencia es 1, el cuarto es 2, el quinto es 3, y así sucesivamente... (0, 1, 1, 2, 3, 5, 8, 13, …).

Esto significa que si pasas 6, entonces el sexto elemento en la secuencia de Fibonacci seria 8: 

const Fibonaccirecursivo = (n) => {
  if (n < 2) {
    return n;
  }
  return Fibonaccirecursivo(n - 1) + Fibonaccirecursivo(n - 2);
};

console.log(Fibonaccirecursivo(6)); // 8

En el código anterior, el algoritmo especifica una tasa de crecimiento que se duplica cada vez que se agrega el conjunto de datos de entrada. Esto significa que la complejidad del tiempo es exponencial con orden O (2 ^ n).

Para terminar

En esta guía, has aprendido de qué se trata la complejidad del tiempo, cómo se determina el rendimiento utilizando la notación Big O y las diversas complejidades del tiempo que existen con ejemplos.

Puede obtener más información a través del plan de estudios sobre Estructuras de Datos y Algoritmos de JavaScript de freeCodeCamp.

¡Feliz codificación!