BigO.md

Big O

• Complejidad del Algoritmo
• Mide Tiempo y Espacio
• Medimos a través de la curva de crecimiento de los pasos que va tener que hacer el algoritmo.
• Por ejemplo: Un input de 5 elementos hace 5 pasos, y de 15 elementos hace 100 pasos.
• No contamos constantes.
• Siempre hablamos de el peor caso

Categorización

O(1)

• Nunca crece, siempre se mantiene igual
• console.log('hola')

  function mostrarMillon(){ // O(1)
    for (var i = 0; i < 1000000; i++){ // O(1)
      console.log(i); // O(1)
    }
  }

O(n)

• Lineal
• Siempre la cantidad de pasos aumenta igual que n

  function mostrarArreglo(arr) { // O(n)
    for (var i = 0; i < arr.length; i++) { // O(n)
      console.log(arr[i]); // O(1)
    }
  }

  function mostrarArreglo(arr) { // O(n)
    for (var i = 0; i < arr.length; i++) { // O(n)
      for (var j = 0; j < 10; j++) { // O(1)
        console.log(arr[i]); // O(1)
      }
    }
  }

O(log n)

• Normalmente con busquedas binarias
• Estructura de Dato: Arbol binario
• Arreglos Ordenados

O(n*log n)

• Merge Sort
• Esta entre O(n) y O(n^2)

O(n^2)

• Hacer N veces algo, N veces.
• Bubble Sort
• For Loops anidados

function loopAnidados(arr) { // (n^2)
  for (var i = 0; i < arr.length; i++) { // O(n)
    for (var j = 0; j < arr.length; j++) { // O(n)
      console.log(arr[j]); // O(1)
    }
  }
}

O(2^n)

• La vision opuesta al arbol binario

function fibonacci (n) {
  if (n === 0 || n === 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

O(n!)

• Factorial: 5! = 5*4*3*2*1
• Permutar todas las posibilidades

Como sacar el Big O

• Ir linea por linea sacando el Big O
• Y quedarse con el mas grande sin tener en cuenta las constantes.

  function dosLoops(arr) { // O(n+n) = O(2n) = O(n)
    for (var i = 0; i <arr.length; i++) { //O(n)
      // hacer algo O(1)...
    }
    for (var i = 0; i <arr.length; i++) { // O(n)
      // hacer algo O(1)...
    }
  }

Muiltivariables

• Tener dos variables que afectan la complejidad

O(n+m)

function(arr1,arr2) {
  for (var i = 0; i < arr1.length; i++ ){
    // algo...
  }
  for (var i = 0; i < arr2.length; i++ ){
    // algo...
  }
}

O(n*m)

function(arr1, arr2) {
  for (var i = 0; i < arr1.length; i++){
    for (var j = 0; j < arr2.length; j++) {
      // algo...
    }
  }
}

Espacio

• Cuanto puede crecer el tamaño de un arreglo/objeto
• El llamado de funciones (call stack)

function fibonacci (n) { // O(n)
  if (n === 0 || n === 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2); // O(n)
}

function crearArreglo(arr) {
  const arrNuevo = [];
  for (var i = 0; arr.length > i; i++) {
    arrNuevo.push(arr[i]);
  }
}