BigO.md

Big O

Que es?

• Para calcular la eficacia de un algoritmo
• En tiempo o espacio
• Calculamos el tiempo con numero de operaciones
• Habla de curva de crecimiento dependiendo el input
• Medimos el peor caso
• No importan las constates

Categorias

• O(1)
  • lineal
  • nunca cambia no importa el tamaño del input
• O(logn)
  • logaritmico
  • Arbol binario
  • Muchas veces lo pueden utilizar con arreglos ordenados
• O(n)
  • Siempre aumenta igual que el input
  • puede ser 6n 100000n pero sigue siendo lineal
• O(n * logn)
  • merge sort
• O(n^2)
  • cuadrática
  • Normalmente loops anidados
• O(n^3 n^4 ....)
  • polinomico
• O(2^n)
  • exponencial
• O(n!)
  • 5! = 54321 =120
  • 6 = 6*5... = 720
  • Torre Hanoi
  • Permutar entre todas las posiblidades

Como encontrarlo?

• Ver cada linea de nuestro codigo
• Una por una calcular el Big O
• No incluir constantes

    function logElems(arr) { // O(n)
        arr.forEach(elem => { // O(n)
            console.log(elem); O(1)
        });
    }

    function logElems(arr) { // O(n)
        arr.forEach(elem => { // O(n)
            console.log(elem); O(1)
        });
        arr.forEach(elem => { // O(n)
            console.log(elem); O(1)
        });
    }

    
    function logElems (arr) {
        for(let i = 0; i < 100000; i += 1) { // O(1)
            console.log(arr[i]);
        }
    }

Multivariables

    
    function logElems(arr) { // O(n * m)
        arr.forEach(elem => { // O(n)
            console.log(elem); // O(1)
            for( let i = 0; i < elem.length; i ++) { // O(m)
                console.log(elem[i]); // O(1)
            }
        });
    }

    function logElems(arr1, arr2) { // O(n + m)
        arr1.forEach(elem => { // O(n)
            console.log(elem); O(1)
        });
        arr2.forEach(elem => { // O(m)
            console.log(elem); O(1)
        });
    }

Espacio

• Medimos como crece el espacio que ocupamos a medida que crece el input
• No contamos los input en si.
• Nuevas variables
• Call Stack --> relacionado con el stack overflow

    function fibonacci (n) {
        if (n === 0) return 0; // tiempo O(1) espacio O(1)
        else if (n === 1) return 1; // tiempo O(1) espacio O(1)
        return fibonacci(n - 1) + fibonacci(n - 2); // tiempo O(n^2) espacio O(n)
    }

    
    function createNewArray(arr) { // tiempo O(n) espacio O(n)
        const newArr = [];
        for (let i  = 0; i <arr.length; i += 1) { // O(n)
            newArr.push(arr[i]); // espacio O(n)
        }
        return newArr;
    }