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.
