La notación O grande con ejemplos en JavaScript

Después de mi anterior post sobre complejidad computacional, hoy voy a hablar de la notación O grande, que es una notación matemática que nos ayuda a describir el comportamiento de un algoritmo "al límite" en función de sus elementos de entrada N.

Algunos de los órdenes más utilizados en análisis de algoritmos, en orden creciente, están resumidos en la siguiente tabla:

notación	nombre
O(1)	constante
O(log n)	logarítmico
O(n)	lineal
O(n log n)	lineal logarítmico
O(n^2)	cuadrático
O(2^n)	exponencial
O(n!)	factorial

A continuación tenéis un vídeo en inglés en dónde se explica la notación O grande y como saber el orden de un algorítmo estudiando su código con reglas sencillas. Luego yo después muestro varios ejemplos de algoritmos de distintos tipos de orden.

Ejemplo de un algoritmo de orden O(1)

Imaginemos un programa que dado un número N, saca dicho número por pantalla. Para simular que el programa hace "algo", antes de sacar dicho número por pantalla, vamos a hacer que llame a una función llamada "retraso" que cree un array con los 999.999 primeros números naturales.

function retraso() {
    let max = 999999;
    let array = new Array(max);
    for (let index = 0; index < array.length; index++) {
        array[index] = index;
    }
}

function ejecutar(n) {
    let inicio = new Date();
    retraso();
    console.log(n);
    let fin = new Date();
    let miliseconds = fin.getTime() - inicio.getTime();
    console.log(miliseconds + " miliseconds");
}

ejecutar(10);
ejecutar(1000);
ejecutar(100000);
ejecutar(10000000);

El programa lo ejecutamos para N=10, N=1.000, N=100.000 y N=10.000.000, sacando por pantalla en cada caso el número de milisegundos que ha tardado en ejecutarse.

10
11 miliseconds
1000
5 miliseconds
100000
6 miliseconds
10000000
5 miliseconds

Como vemos, este algoritmo es de orden O(1), constante, pues da igual el número de entrada, siempre va a tardar más o menos lo mismo en ejecutarse.

Ejemplo de un algoritmo de orden O(log N)

Imaginemos el mismo programa de antes, solo que ahora guarda en un array la división de N por 2, y luego la división del resultado obtenido por 2, y así sucesivamente hasta que el resultado sea menor que 1. Para simular que el programa hace "algo", antes de asignar un número al array, vamos a hacer que llame a una función llamada "retraso" que cree un array con los 999.999 primeros números naturales.

function retraso() {
    let max = 999999;
    let array = new Array(max);
    for (let index = 0; index < array.length; index++) {
        array[index] = index;
    }
}

function ejecutar(n) {
    let inicio = new Date();
    let array = [];
    let resultado = n;
    while (resultado > 1) {
        retraso();
        resultado = resultado / 2;
        array.push(resultado);
    }
    let fin = new Date();
    let miliseconds = fin.getTime() - inicio.getTime();
    console.log(n);
    console.log(miliseconds + " miliseconds");
}

ejecutar(10);
ejecutar(1000);
ejecutar(100000);
ejecutar(10000000);

El programa lo ejecutamos para N=10, N=1.000, N=100.000 y N=10.000.000, sacando por pantalla en cada caso el número de milisegundos que ha tardado en ejecutarse.

10
22 miliseconds
1000
47 miliseconds
100000
84 miliseconds
10000000
127 miliseconds

Como vemos, este algoritmo es de orden O(log N), logarítmico, pues el tiempo de ejecución depende logarítmicamente del número de entrada (si multiplicamos N por 100 el tiempo de ejecución aproximadamente solo se duplica).

Ejemplo de un algoritmo de orden O(N)

Imaginemos el mismo programa de antes, solo que ahora guarda un array con los N primeros números naturales. Para simular que el programa hace "algo", antes de asignar un número al array, vamos a hacer que llame a una función llamada "retraso" que cree un array con los 999.999 primeros números naturales.

function retraso() {
    let max = 999999;
    let array = new Array(max);
    for (let index = 0; index < array.length; index++) {
        array[index] = index;
    }
}

function ejecutar(n) {
    let inicio = new Date();
    let array = new Array(n);
    for (let index = 0; index < n; index++) {
        retraso();
        array[index] = index;
    }
    let fin = new Date();
    let miliseconds = fin.getTime() - inicio.getTime();
    console.log(n);
    console.log(miliseconds + " miliseconds");
}

ejecutar(1);
ejecutar(10);
ejecutar(100);
ejecutar(1000);

El programa lo ejecutamos para N=1, N=10, N=100 y N=1.0000, sacando por pantalla en cada caso el número de milisegundos que ha tardado en ejecutarse.

1
7 miliseconds
10
49 miliseconds
100
584 miliseconds
1000
6076 miliseconds

Como vemos, este algoritmo es de orden O(N), lineal, pues el tiempo de ejecución depende directamente del número de entrada (si multiplicamos N por 10 el tiempo de ejecución también se multiplica aproximadamente por 10).

Ejemplo de un algoritmo de orden O(N^2)

Imaginemos el mismo programa de antes, solo que ahora guarda un array con todas las combinaciones de multiplicar todos los números naturales igual o menor que N. Para simular que el programa hace "algo", antes de asignar un número al array, vamos a hacer que llame a una función llamada "retraso" que cree un array con los 999.999 primeros números naturales.

function retraso() {
    let max = 999999;
    let array = new Array(max);
    for (let index = 0; index < array.length; index++) {
        array[index] = index;
    }
}

function ejecutar(n) {
    let inicio = new Date();
    let array = new Array(n*n);
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= n; j++) {
            retraso();
            array.push(i*j);
        }
    }
    let fin = new Date();
    let miliseconds = fin.getTime() - inicio.getTime();
    console.log(n);
    console.log(miliseconds + " miliseconds");
}

ejecutar(2);
ejecutar(4);
ejecutar(8);
ejecutar(16);

El programa lo ejecutamos para N=2, N=4, N=8 y N=16, sacando por pantalla en cada caso el número de milisegundos que ha tardado en ejecutarse.

2
46 miliseconds
4
125 miliseconds
8
487 miliseconds
16
1702 miliseconds

Como vemos, este algoritmo es de orden O(N^2), cuadrático, pues el tiempo de ejecución depende cuadráticamente del número de entrada (si multiplicamos N por 2 el tiempo de ejecución se multiplica aproximadamente por casi 4).