Big O - ejemplos básicos

Ver explicación sobre "Big O" antes de profundizar en estos ejemplos básicos de algoritmos.

O(1) - constante

Es el mejor resultado, y quiere decir que el tiempo de ejecución no varía conforme aumenta el tamaño de los datos de entrada, y la respuesta siempre tarda lo mismo sin importar la magnitud de entrada.

Ejemplo: Acceso directo en un array de datos

const fruits = ["apple", "orange", "pear", "kiwi", "melon"]

const consoleFirstItem = items => {
  console.log(items[0])
}

consoleFirstItem(fruits)

O(n) - lineal

El crecimiento es lineal en tanto el tiempo de ejecución es cada vez mayor de modo proporcional a cómo se incrementa el tamaño de la entrada. Por lo que si tenemos el doble de elementos de entrada, tardará el doble, aunque despreciamos realmente la pendiente de la misma y sólo nos quedamos con que aumenta de forma lineal.

Ejemplo: recorrer un array en un ciclo for

Tanto en el caso de un valor de entrada de tamaño N

function consoleNumbersTo(n) {
  for (let i = 1; i <= n; i++) {
    console.log(i)
  }
}

consoleNumbersTo(10)

O igualmente un array de N elementos

const fruits = ["apple", "orange", "pear", "kiwi", "melon"]

const consoleAlltItems = items => {
  items.forEach(item => console.log(item))
}

consoleAlltItems(fruits)

No importa si en cada ciclo realizamos más o menos trabajo ya que aunque pudiera parecer que tenemos un logaritmo que tarda el doble o el triple, algo como O(3n) lo simplificamos a O(n)

function consoleNumbersTo(n) {
  for (let i = 1; i <= n; i++) {
    console.log(i)
  }
  for (let i = 1; i <= n; i++) {
    console.log(i)
  }
  for (let i = 1; i <= n; i++) {
    console.log(i)
  }
}

consoleNumbersTo(10)

O(n^2) - cuadrática

El crecimiento es de forma exponencial por lo que será un algoritmo a evitar ya que para valores pequeños de entrada el tiempo será asumible, pero conforme aumente el tamaño de los datos de entrada el tiempo tenderá a ser muy elevado y es probable que el procesador se quede inoperativo.

Ejemplo: recorrer un ciclo for anidado a otro

function consoleMultiplicationOf(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      console.log(`${i} * ${j} = ${i * j}`)
    }
  }
}

consoleMultiplicationOf(10)

const fruits = ["apple", "orange", "pear", "kiwi", "melon"]
const isVowel = char => ["a", "e", "i", "o", "u"].includes(char.toLowerCase())

const consoleAllVowels = items => {
  items.forEach(item => {
    item.split("").forEach(char => {
      if (isVowel(char)) {
        console.log(char)
      }
    })
  })
}

consoleAllVowels(fruits)

Del mismo modo si tenemos un algorítmo que primero hace una operación O(n) y seguidamente otro paso de O(n^2), al final lo simplificamos al más desfavorable: O(n+n^2) -> O(n^2)

function consoleMultiplicationOf(n) {
  for (let i = 1; i <= n; i++) {
    console.log(i)
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      console.log(`${i} * ${j} = ${i * j}`)
    }
  }
}

consoleMultiplicationOf(10)

Aunque a efectos de análisis de Big O las constantes de tiempo se desprecien, en la realidad esta constante sí que puede ser importante si por ejemplo supone un tiempo significativo que haga un algorítmo reducir o ampliar el tiempo que tarda en procesarse en base a por ejemplo a esos pasos extras que amplian el tiempo.

Peor caso

En general hablamos siempre del peor de los casos, porque podemos tener algoritmos de busqueda que en ocasiones encuentren el elemento buscado a la primera lo que sería en un O(1) pero en otros casos que tiene que ir hasta el último elemento, y será este el que normalmente se usa para especificar el valor Big O de un algoritmo, atendiendo al peor de los casos.

Ejemplo: buscando un elemento recorriendo todos los datos

const fruits = ["apple", "orange", "pear", "kiwi", "melon"]

const bruteSearch = (arr, item) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === item) {
      return `Found ${item} at ${i + 1}`
    }
  }
}

bruteSearch(fruits, "kiwi")

O(log n) - logarítmica

Una forma de crecimiento que crece al inicio pero tiende a estabilizarse conforme aumentan el tamaño de entrada, por lo que es una buena nota para un algoritmo ya que no tiende a resentirse.

El ejemplo anterior mejorado sustancialmente usando: Binary Search

Se llama busqueda binaria o busqueda logarítmica, ya que no aumenta apenas conforme aumenta el tamaño de los datos a evaluar, con motivo de que los datos de partida están ordenados, y que en cada paso descarta la mitad de los datos: compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

Dada la complejidad del mismo si no se ha visto antes, lo mejor es tratarlo en un artículo aparte. :)

function binarySearch(sortedArray, key) {
  let start = 0
  let end = sortedArray.length - 1

  while (start <= end) {
    let middle = Math.floor((start + end) / 2)

    if (sortedArray[middle] === key) {
      // found the key
      return middle
    } else if (sortedArray[middle] < key) {
      // continue searching to the right
      start = middle + 1
    } else {
      // search searching to the left
      end = middle - 1
    }
  }
  // key wasn't found
  return -1
}

Si te ha gustado... ¡Compártelo!