Una introducción visual a la notación Big O

• La notación Big O expresa el rendimiento de una función como su patrón de crecimiento según cambia el tamaño de la entrada
• El artículo explica, con ejemplos, los casos más representativos de Big O: constante, logarítmico, lineal y cuadrático
• La complejidad temporal varía según la estructura de datos y el algoritmo, y se nota en tareas como ordenar o buscar en arreglos
• Para mejorar el rendimiento real del código, lo más importante es elegir la estructura de datos adecuada y eliminar operaciones innecesarias dentro de los bucles
• Big O siempre representa de la forma más simplificada posible la relación entre la entrada y el tiempo de ejecución, y al optimizar el rendimiento es importante medir el código directamente

---

Descripción general de la notación Big O

• La notación Big O es una forma de describir el patrón de crecimiento del tiempo de ejecución según el tamaño de la entrada (n), en lugar de medir el tiempo directamente
• Clasifica el tiempo de ejecución de una función según la entrada, y por lo general se analizan formas como constante (O(1)), logarítmica (O(log n)), lineal (O(n)) y cuadrática (O(n²))
• Este artículo lo explica con conceptos, ejemplos visuales y ejemplos de código reales para que incluso principiantes puedan entender cada caso

Iteración y algoritmos lineales

• La función sum(n) es un ejemplo de una estructura iterativa que suma de 1 a n, y a medida que crece el valor de entrada n, el tiempo de ejecución también aumenta en proporción directa
• En la práctica, sum(1e9) tarda alrededor de 1 segundo y sum(2e9) unos 2 segundos, por lo que el tiempo de reloj (wall-clock time) crece con un patrón O(n)
• La complejidad temporal es la relación entre la entrada de una función y su tiempo de ejecución, y se expresa con la notación Big O (O(n) — proporcional a n)
• En lugar de iterar, usar la fórmula matemática sum(n) = (n*(n+1))/2 hace que el tiempo de ejecución sea constante e independiente del valor de entrada n
• A este tipo de función se le llama complejidad temporal constante O(1), y su rasgo principal es que el tiempo de ejecución no crece cuando cambia la entrada

Sintaxis de la notación Big O

• La O de Big O viene de “Order” (orden de crecimiento) y solo indica la forma del crecimiento en sí
• No representa el valor absoluto del tiempo de ejecución, sino solo el 'patrón' de crecimiento respecto a la entrada de manera concisa
• Por ejemplo, aunque una función sea O(n), no se escribe de forma complicada como 'O(2n)' o 'O(n+1)', sino que se elige solo el término más simple

Reducir el tiempo usando la estructura de la entrada

• Como en el ejemplo de la fórmula de sum(n), mejorar el algoritmo puede cambiar la complejidad temporal de O(n) a O(1)
• Sin embargo, tener complejidad constante no significa automáticamente que siempre sea más rápido; el tiempo total también depende del tipo de operación
• Un algoritmo O(n) puede ser más rápido que uno O(1) para cierta entrada, pero cuando el tamaño de la entrada crece, el enfoque O(1) siempre termina imponiéndose

Ordenamiento y algoritmos cuadráticos: ejemplo de Bubble Sort

• Bubble Sort es un ejemplo básico de ordenamiento que organiza un arreglo repitiendo intercambios entre elementos adyacentes
• Si el arreglo ya está ordenado, basta 1 pasada (O(n)); si está en orden inverso, hace falta recorrerlo n veces repetidamente → en el peor caso, el total de operaciones es n²
• Un algoritmo O(n²) aumenta mucho su tiempo de ejecución en forma cuadrática a medida que crece la entrada
• En el uso real, Big O siempre se basa en el peor caso (worst-case), aunque a veces también se indiquen el caso promedio o el mejor caso
• Aunque la cantidad de pasadas puede reducirse según el estado inicial del arreglo, por considerar el peor caso siempre se clasifica como complejidad temporal cuadrática

Búsqueda y algoritmos logarítmicos: ejemplo de búsqueda binaria

• La búsqueda binaria (Binary Search) estima el valor central de un rango ordenado y en cada paso descarta la mitad del espacio candidato
• Por ejemplo, para adivinar un número específico entre 1 y 100 se necesitan como máximo 7 intentos, y entre 1 y 1,000 millones también se puede lograr en menos de 31 intentos
• Como en cada paso la lista candidata se reduce a la mitad, el tiempo de ejecución es O(log n) (complejidad logarítmica)
• Los algoritmos logarítmicos muestran un crecimiento extremadamente lento cuando n aumenta, por lo que son mucho más eficientes que los lineales o cuadráticos
• Al comparar gráficas, la diferencia de crecimiento entre log n, n y n² se vuelve muy evidente

Aplicación práctica: consejos para mejorar la complejidad temporal

Buscar elementos en una lista

• De forma básica, una función que busca un valor en un arreglo corresponde a O(n)
• Si la búsqueda es frecuente, usar una estructura de datos como Set permite mejorar a O(1)
• Sin embargo, el proceso de conversión con new Set(array) es en sí mismo O(n), así que solo conviene cuando habrá consultas frecuentes (hay que considerar el costo de conversión)
• Ejemplo: items.has("banana") ofrece complejidad temporal constante

Escribir bucles aprovechando el índice

• Es común que código como el siguiente, que usa .indexOf dentro del bucle, sea una causa de problemas de rendimiento

  function buildList(items) {
    const output = [];
    for (const item of items) {
      const index = items.indexOf(item);
      output.push(`Item ${index + 1}: ${item}`);
    }
    return output.join("\n");
  }
  

• Como .indexOf es una operación O(n) dentro del bucle, en conjunto se convierte en un patrón O(n^2)

• Al usar iteración basada en índice o forEach((item, index) => ...), se mejora a O(n)

  function buildList(items) {
    const output = [];
    for (let i = 0; i < items.length; i++) {
      output.push(`Item ${i + 1}: ${items[i]}`);
    }
    return output.join("\n");
  }
  

Uso de memoización

• En estructuras con cálculos repetidos, como el factorial cuando se llama varias veces, se puede mejorar el rendimiento aplicando caché de resultados (usando Map)

• Las consultas en Map corresponden a O(1), por lo que se minimiza el recálculo innecesario

• Sin embargo, el caché ayuda a mejorar el tiempo promedio y, aunque la complejidad temporal del peor caso no cambie, sí puede aportar una mejora eficiente del rendimiento

  const cache = new Map();
  function factorial(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }
    if (n === 0) {
      return 1;
    }
    const result = n * factorial(n - 1);
    cache.set(n, result);
    return result;
  }
  

Evaluación del rendimiento y conclusión

• Al mejorar el rendimiento del código, además de la complejidad temporal teórica, hay que confirmar con pruebas de ejecución directas si realmente hubo mejora
• Big O expresa de la manera más esencial y simplificada el patrón de relación y crecimiento entre la entrada y el tiempo de ejecución
• Elegir un buen algoritmo y optimizar la estructura de datos permite maximizar la eficiencia del código

Resumen

• La notación Big O expresa la relación entre la entrada de una función y su tiempo de ejecución
• Principales niveles de rendimiento: O(1) (constante), O(log n) (logarítmico), O(n) (lineal), O(n^2) (cuadrático)
• Para escribir código eficiente, es importante elegir el algoritmo adecuado y optimizar los bucles
• El rendimiento real debe medirse directamente para verificar si hubo mejora
• Usar gráficas comparativas de crecimiento ayuda a entender de un vistazo las características de la complejidad temporal