Publicado el

Notación Big O en JavaScript

Autores

Notación Big O

La Notación Big O, también conocida como notación de Bachmann-Landau o notación asintótica, es una forma de describir el rendimiento de un algoritmo. Se utiliza para describir el peor escenario de un algoritmo. También se usa para comparar el rendimiento de diferentes algoritmos. Describe la implementación de un algoritmo en términos del tamaño de la entrada.

La notación Big O caracteriza las funciones según sus tasas de crecimiento: las tareas con la misma tasa de crecimiento se consideran del mismo orden. Es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o hacia el infinito. Se utiliza para clasificar los algoritmos de acuerdo con cómo su tiempo de ejecución o requisitos de espacio crecen a medida que crece el tamaño de la entrada. La letra O se usa porque la tasa de crecimiento de una función también se llama su orden.

Iteración

Bucle for

for (let i = 0; i < n; i++) {
  console.log(i)
}

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Bucle while

let i = 0
while (i < n) {
  console.log(i)
  i++
}

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Bucle do while

let i = 0
do {
  console.log(i)
  i++
} while (i < n)

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Recursión

Factorial

function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
}

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Fibonacci

function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Búsqueda

Búsqueda lineal

function linearSearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return i
    }
  }
  return -1
}

El código anterior se ejecutará n veces. La complejidad temporal de este código es O(n).

Búsqueda binaria

function binarySearch(arr, value) {
  let start = 0
  let end = arr.length - 1
  let middle = Math.floor((start + end) / 2)
  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1
    } else {
      start = middle + 1
    }
    middle = Math.floor((start + end) / 2)
  }
  if (arr[middle] === value) {
    return middle
  }
  return -1
}

El código anterior se ejecutará log(n) veces. La complejidad temporal de este código es O(log(n)).

Ordenación

Ordenación de burbuja

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

El código anterior se ejecutará n^2 veces. La complejidad temporal de este código es O(n^2).

Ordenación por selección

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      let temp = arr[i]
      arr[i] = arr[lowest]
      arr[lowest] = temp
    }
  }
  return arr
}

El código anterior se ejecutará n^2 veces. La complejidad temporal de este código es O(n^2).

Ordenación por inserción

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
  }
  return arr
}

El código anterior se ejecutará n^2 veces. La complejidad temporal de este código es O(n^2).

Ordenación por mezcla

function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  let results = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      results.push(left[i])
      i++
    } else {
      results.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    results.push(left[i])
    i++
  }
  while (j < right.length) {
    results.push(right[j])
    j++
  }
  return results
}

El código anterior se ejecutará n log(n) veces. La complejidad temporal de este código es O(n log(n)).

Ordenación rápida

function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start]
  let swapIdx = start
  function swap(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
  }
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++
      swap(arr, swapIdx, i)
    }
  }
  swap(arr, start, swapIdx)
  return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
}

El código anterior se ejecutará n log(n) veces. La complejidad temporal de este código es O(n log(n)).

Consejos para Big O

  • Las operaciones aritméticas son constantes.
  • La asignación de variables es constante.
  • El acceso a elementos en un arreglo (por índice) u objeto (por clave) es constante.
  • En un bucle, la complejidad es la longitud del bucle multiplicada por la complejidad de lo que sucede dentro del bucle.

Recursos

Comentar en Twitter

COMPARTIR