馃敟 BIG O (INTRODUCCI脫N)

La notaci贸n Big O es una estrategia para normalizar el conteo difuso. Nos permite abordar como el tiempo de ejecuci贸n de un algoritmo es proporcional a sus valores de entrada, es decir como crece dicho tiempo de ejecuci贸n conforme los valores cambian.

Decimos que un algoritmo es O(f(n)) si el n煤mero de operaciones simples que tiene que hacer el ordenador es eventualmente menor que una constante veces f(n), a medida que n aumenta.

Las opciones posibles son:

  • f(n) puede ser linear (f(n) = n)
  • f(n) puede ser cuadr谩tica (f(n) = n^2)
  • f(n) puede ser constante (f(n) = 1)
  • f(n) puede ser algo distinto

En las funciones de la lecci贸n anterior, la funci贸n que utiliza el bucle para realizar la suma de n煤meros crece de forma linear conforme n se incrementa, podemos decir que es una funci贸n O(n).

function sumarNumeros(n) {
    let suma = 0;
    for (let i = 0; i <= n; i++) {
        suma += i;
    }
    return suma;
}

Si bien la funci贸n anterior deber铆a ser expresada como 5n+2, al momento de utilizar Big O solo debemos enfocarnos en el comportamiento general, por lo cual expresar O(n) es correcto.

Por su parte la segunda funci贸n mantiene su tiempo de ejecuci贸n constante independientemente si n aumenta o no, por lo que es una funci贸n O(1).

function sumarNumeros(n) {
    return (n * (n + 1)) / 2;
}

Analicemos ahora otra funci贸n en esta ocasi贸n vamos a construir una matriz igual en dimensiones X y Y proporcional a n. Para este ejemplo tenemos un for anidado, lo que implica una operaci贸n O(n) dentro de otra operaci贸n O(n). Este tipo de algoritmo tiene una notaci贸n O(n^2) que representa un incremento bastante considerable en relaci贸n a uno linear O(n).

function llenarMatriz(n) {
    const matriz = [];
    let total = 1;
    for (let i = 0; i < n; i++) {
        matriz[i] = [];
        for (let j = 0; j < n; j++) {
            matriz[i][j] = total++;
        }
    }
    return matriz;
}

驴C贸mo simplificar las expresiones Big O?

Cuando deseamos determinar la complejidad de un algoritmo existen algunos atajos que nos permiten simplificar en expresiones Big O.

Las constantes no son importantes

  • O(2n) es igual a O(n)
  • O(500) es igual a O(1)
  • O(5n^2) es igual a O(n^2)

Lo importante es determinar la tendencia y saber cual de las expresiones es mas r谩pida y cual la menos eficiente.

T茅rminos peque帽os no importan

  • O(n + 5) es igual a O(n)
  • O(20n + 10) es igual a O(n)
  • O(5n^2 + 10n + 2) es igual a 0(n^2)

Atajos importantes para considerar en Big O

  • Los operadores aritm茅ticos son constantes
  • La asignaci贸n de variables es constante
  • Acceder a los valores de un diccionario o arreglo a trav茅s de su indice es constante.
  • En un ciclo la complejidad es el resultado de multiplicar el n煤mero de iteraciones por la complejidad del scope del ciclo.