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 |
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 milisecondsComo 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 milisecondsComo 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 milisecondsComo 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 milisecondsComo 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).
