Big O notation examples JavaScript: Ejemplos de notación Big O en JavaScript 2025

En este post, Big O notation examples JavaScript aprenderás cómo aplicar la notación Big O a tus algoritmos en JavaScript.

☝️ Si estás preparándote para una entrevista técnica, comprender la notación Big O es lo que va a marcar la diferencia entre el éxito o el fracaso.

Introducción a la Big O Notation

La Big O notation es una forma de describir la eficiencia de un algoritmo en términos de cuánto tiempo o espacio requiere en función del tamaño de la entrada.

Una buena manera de pensar en la notación Big O es leyendo paso a paso el algoritmo y contar cuántas operaciones realiza en función del tamaño de la entrada.

Más allá de entrevistas de algoritmos y estructuras de datos, la notación Big O es una herramienta esencial para optimizar el rendimiento de tu código y escalar aplicaciones en la vida real.

Por ejemplo: Si tienes una aplicación (web, mobile, etc) y tienes un algoritmo que toma 1 segundo para 10 elementos, ¿cuánto tiempo tomará para 1000 elementos? ¿Y para 1 millón de elementos? La notación Big O te ayudará a responder estas preguntas.

Conceptos y notaciones fundamentales de la Big O Notation

No te preocupes si suena demasiado técnico o complejo al inicio. Aquí te explico paso a paso y con ejemplos, pero antes es importante comprender los conceptos básicos.

Big O mide la eficiencia de un algoritmo en términos de tiempo y espacio.

• Time complexity: Mide cuánto "tiempo" toma un algoritmo en función del tamaño de la entrada (no en términos de segundos, sino de el número de operaciones que un algoritmo realiza en función al input de entrada, más en los ejemplos...).
• Space complexity: Mide cuánta memoria (espacio) toma un algoritmo en función del tamaño de la entrada.

Y aquí están las notaciones fundamentales de la Big O notation:

• O(1): Tiempo constante. No importa el tamaño de la entrada, el tiempo de ejecución es siempre el mismo.
• O(n): Tiempo lineal. El tiempo de ejecución aumenta linealmente con el tamaño de la entrada.
• O(n^2): Tiempo cuadrático. El tiempo de ejecución aumenta cuadráticamente con el tamaño de la entrada.
• O(log n): Tiempo logarítmico. El tiempo de ejecución disminuye logarítmicamente con el tamaño de la entrada.
• O(n log n): Tiempo log-lineal. El tiempo de ejecución aumenta logarítmicamente con el tamaño de la entrada.
• O(n!): Tiempo factorial. El tiempo de ejecución aumenta factorialmente con el tamaño de la entrada.

Ahora veamos una gráfica de Big O notation para visualizar mejor cómo se comparan estas complejidades.

Como puedes ver, generalmente debemos evitar algoritmos con complejidades de tiempo altas como O(n^2), O(n!) y en su lugar, buscar algoritmos con complejidades de tiempo bajas como O(1), O(log n) y O(n log n).

Aunque esto siempre va a depender del problema que estemos resolviendo y de las restricciones de tiempo y espacio que tengamos.

Veamos ejemplos de cómo aplicar estos conceptos en JavaScript.

Big O Notation Examples JavaScript: Ejemplo de O(1) o Tiempo constante

La notación O(1) significa que el tiempo de ejecución del algoritmo es constante, no importa el tamaño de la entrada, siempre tomará el mismo tiempo.

const array = [1, 2, 3, 4, 5]
function firstElement(arr) {
  return arr[0]
}
console.log(firstElement(array)) // O(1)

En este ejemplo, no importa si el array tiene 5 elementos o 1000 elementos, la función firstElement siempre tomará el mismo tiempo para devolver el primer elemento del array.

Big O Notation Examples JavaScript: Ejemplo de O(n) o Tiempo lineal

En este ejemplo, la función linearSearch recorre un array y busca un elemento específico. La complejidad de tiempo es O(n) porque recorre cada elemento del array.

Es decir, si el array tiene 5 elementos, la función realizará 5 operaciones. Si el array tiene 1000 elementos, la función realizará 1000 operaciones.

let array = [1, 2, 3, 4, 5]
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i
    }
  }
  return -1
}
console.log(linearSearch(array, 3)) // O(n)

Debido a que la función linearSearch incrementa los pasos en función del tamaño del array, su complejidad de tiempo es O(n), donde n es el número de elementos en el array en este caso.

Big O Notation Examples JavaScript: Ejemplo de O(n^2) o Tiempo cuadrático

En este ejemplo, la función findInMatrix recorre una matriz de 2 dimensiones y busca un elemento específico. La complejidad de tiempo es O(n^2) porque recorre cada fila y cada columna de la matriz.

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
function findInMatrix(mat, target) {
  for (let i = 0; i < mat.length; i++) {
    for (let j = 0; j < mat[i].length; j++) {
      if (mat[i][j] === target) {
        return [i, j]
      }
    }
  }
  return null
}
console.log(findInMatrix(matrix, 5)) // O(n^2)

Debido a que la función findInMatrix incrementa los pasos en función del tamaño de la matriz (n por n), su complejidad de tiempo es O(n^2), donde n es el número de elementos en la matriz en este caso.

Esto significa que si la matriz tiene 3 filas y 3 columnas, la función realizará 9 operaciones. Si la matriz tiene 100 filas y 100 columnas, la función realizará 10000 operaciones.

Big O Notation Examples JavaScript: Ejemplo de O(log n) o Tiempo logarítmico

En este ejemplo, la función binarySearch busca un elemento específico en un array ordenado. La complejidad de tiempo es O(log n) porque divide el array a la mitad en cada paso.

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}
console.log(binarySearch(array, 4)) // O(log n)

En términos generales, esto significa que si el array tiene 9 elementos, la función realizará 3 operaciones (log2(9) = 3). Si el array tiene 1000 elementos, la función realizará 10 operaciones (log2(1000) = 10).

Si no estás satisfecho con la explicación anterior, aquí te comparto más a detalle:

• Si el array tiene 9 elementos, entonces:
  • En el primer paso, la función compara el elemento en la posición 4 (9/2 = 4.5, redondeado a 4).
  • En el segundo paso, la función compara el elemento en la posición 2 (4/2 = 2).
  • En el tercer paso, la función compara el elemento en la posición 3.

Si el array tiene 1000 elementos, entonces:

• En el primer paso, la función compara el elemento en la posición 500.
• En el segundo paso, la función compara el elemento en la posición 250.
• En el tercer paso, la función compara el elemento en la posición 375.
• Y así sucesivamente.

Big O Notation Examples JavaScript: Ejemplo de O(n log n) o Tiempo log-lineal

En este ejemplo, la función quickSort ordena un array de forma recursiva utilizando el algoritmo de ordenamiento rápido.

Quicksort u orderamiento rápido es un algoritmo de ordenamiento muy eficiente basado en la técnica de divide y vencerás, y la partición de Hoare.

En español simple, esto es lo que hace:

1. Divide el array en partes más pequeñas usando un elemento pivote y luego ordena estas partes recursivamente.
2. Combina las partes ordenadas para obtener el array final ordenado.

La complejidad de tiempo es O(n log n) porque divide el array a la mitad en cada paso y realiza n comparaciones en cada división.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let pivot = arr[Math.floor(arr.length / 2)]
  let left = arr.filter((x) => x < pivot)
  let right = arr.filter((x) => x > pivot)
  return [...quickSort(left), pivot, ...quickSort(right)]
}
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])) // O(n log n)

Esto significa que si el array tiene 7 elementos, la función realizará 7 * log2(7) = 7 * 2.8 = 19.6 operaciones.

Si el array tiene 1000 elementos, la función realizará 1000 * log2(1000) = 1000 * 10 = 10000 operaciones.

Consejos para Optimizar el Código en JavaScript Usando Big O Notation

Es muy importante comprender el problema que queremos resolver, porque esto va a determinar la estructura de datos y el algoritmo a utilizar.

Pero ojo, NO MEMORIZES los algoritmos y sus complejidades, más bien entiende cómo funcionan y cuándo usarlos.

Aquí tienes una guía de pensamiento para ayudarte a elegir el algoritmo correcto:

1. Tamaño de los Datos: Para pequeños conjuntos de datos, la diferencia entre (O(n)) y (O(n log n)) puede ser mínima, pero para grandes conjuntos, esta diferencia es crucial.

2. Operaciones Comunes: Si necesitas accesos rápidos, busca algoritmos con complejidad (O(1)) o (O(log n)).

3. Recurso Limitado: Si el espacio en memoria es una limitación, elige algoritmos con baja complejidad espacial.

4. Escalabilidad: Un algoritmo que parece eficiente con pequeños datos puede volverse ineficiente a medida que los datos aumentan.

5. Peor Caso vs Promedio: Considera tanto el peor caso como el promedio de rendimiento del algoritmo, por norma general, siempre se toma en cuenta el peor caso.

Ahora bien, es importante que elijas la estructura de datos adecuada para el problema que estás resolviendo. Aquí tienes una guía rápida:

1. Arrays: Buena opción para acceso aleatorio, pero no para inserciones y eliminaciones frecuentes.
2. Listas Enlazadas: Buena opción para inserciones y eliminaciones frecuentes, pero no para acceso aleatorio.
3. Árboles: Buena opción para búsquedas rápidas y ordenadas.
4. Tablas Hash: Buena opción para búsquedas rápidas y únicas.
5. Colas y Pilas: Buena opción para operaciones FIFO y LIFO.
6. Grafos: Buena opción para problemas de redes y relaciones.
7. Árboles AVL: Buena opción para búsquedas rápidas y balanceadas.

En JavaScript, puedes utilizar las estructuras de datos nativas como Array, Object, Map y Set. Pero también puedes implementar tus propias estructuras de datos si es necesario.

Ejemplos de implementaciones de estructuras de datos en JavaScript:

Lista enlazada en JavaScript

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
  }

  add(value) {
    const node = new Node(value)
    if (!this.head) {
      this.head = node
    } else {
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
  }

  remove(value) {
    if (!this.head) {
      return
    }
    if (this.head.value === value) {
      this.head = this.head.next
      return
    }
    let current = this.head
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next
        return
      }
      current = current.next
    }
  }

  print() {
    let current = this.head
    while (current) {
      console.log(current.value)
      current = current.next
    }
  }
}

const list = new LinkedList()
list.add(1)
list.add(2)
list.add(3)
list.remove(2)
list.print()

Tabla Hash en JavaScript

Esto es sólo un ejemplo, puedes implementar una tabla hash más avanzada con manejo de colisiones y rehashing.

class HashTable {
  constructor() {
    this.table = Object.create(null) // Crear un objeto sin prototipo
  }

  set(key, value) {
    this.table[key] = value
  }

  get(key) {
    return this.table.hasOwnProperty(key) ? this.table[key] : undefined
  }

  remove(key) {
    if (this.table.hasOwnProperty(key)) {
      delete this.table[key]
      return true
    }
    return false
  }

  hasKey(key) {
    return this.table.hasOwnProperty(key)
  }
}

// Uso del hashtable
const ht = new HashTable()
ht.set('name', 'John')
ht.set('age', 30)

console.log(ht.get('name')) // John
console.log(ht.get('age')) // 30

Conclusión

En este post Big O notation examples JavaScript, aprendiste cómo aplicar la notación Big O a tus algoritmos en JavaScript.

Hemos visto ejempuras de complejidades de tiempo como O(1), O(n), O(n^2), O(log n) y O(n log n) con ejemplos de código en JavaScript y cómo elegir la estructura de datos adecuada para tu problema.

Recursos adiconales

¿Quieres profundizar aún más en el estudio de algoritmos y mejorar tus habilidades como desarrollador? Aquí tienes algunos recursos adicionales que te pueden interesar:

• Curso de big O notation en YouTube: Refuerza lo aprendido con mi curso gratuito de Big O notation en YouTube.
• Curso para destacar en entrevistas técnicas en YouTube:Este curso está diseñado para desarrolladores de software que se preparan para entrevistas de código con el fin de conseguir un nuevo trabajo u oportunidad.
• Curso para crear un CV efectivo para que te contraten: Aprende a crear un CV efectivo, incluyendo la plantilla del CV que personalmente uso para conseguir llamadas de entrevistas.
• Grokking Algorithms: Un libro amigable para principiantes que te ayudará a comprender los algoritmos y estructuras de datos de una manera sencilla.

Para ver más sobre los tipos de datos y estructuras en JavaScript, te recomiendo leer la documentación de Mdn Web Docs.