Big O Notation

By March 9, 2019 March 24th, 2019 Algoritmos

¿Qué es el Big O Notation?

Es un lenguaje o nomenclatura utilizada en el ámbito de la programación de sistemas para determinar el “costo” de un algoritmo en términos de tiempo de ejecución y utilización de recursos, en relación a los datos que se van a procesar. Usar el Big O Notation, es una manera medible de expresar la eficiencia de las funciones que creamos, con el fin de saber si son factibles a optimizarlas o rediseñarlas.

Se utiliza esta notación porque en términos reales, hay muchos factores que definen la rapidez de ejecución: tipo de procesador, cantidad de memoria, qué más está corriendo en ese momento, etc. Además, si estamos comparando la eficiencia con relación a los datos de entrada, hablar solo de segundos no es suficiente.

Hay que tomar en cuenta que esta notación se determina considerando el peor de los escenarios, por ejemplo: para buscar un elemento en un arreglo, con suerte lo encontraríamos en la primera posición, pero también podríamos recorrerlo completamente y encontrar el elemento al final del mismo.

Ejemplos en términos de tiempo de ejecución

Ahora veamos algunos ejemplos de las notaciones más comunes y cómo se aplican del mas al menos costoso:

O(1)

Supongamos que tenemos una función que regresa el primer elemento de un arreglo de 100,000 elementos, la función necesitará solamente una iteración para devolver el resultado deseado. Esta es la notación es también llamada constante, porque sin importar qué tan grande sean los datos de entrada, este siempre requerirá solo un paso para procesarlo.

function printFirstItem(allItems) {
  return allItems[0];
}
Búsqueda de un elemento usando un índice
O(1)

O(1)

O(log n)

Esta la encontramos usualmente en funciones que tomen menos iteraciones que la cantidad de datos a procesar. Por ejemplo en una búsqueda binaria en un arreglo ordenado o un árbol binario: [1,3,5,8,9] si buscáramos el #8 lo encontraríamos en 2 iteraciones de 5 posibles.

function binarySearch (list, value) {
    let start = 0
    let stop = list.length - 1
    let middle = Math.floor((start + stop) / 2)

    while (list[middle] !== value && start < stop) {
        if (value < list[middle]) {
            stop = middle - 1
        } else {
            start = middle + 1
        }
        middle = Math.floor((start + stop) / 2)
    }
    return (list[middle] !== value) ? -1 : middle
}
Búsqueda binaria
O(log n)

O(log n)

O(n)

Esta notación es común en funciones que pudieran requerir consumir la totalidad de los datos para entregar un resultado, también llamada lineal. Por ejemplo, una búsqueda de un elemento en un arreglo desordenado, imprimir todos los elementos de un arreglo o una búsqueda lineal.

function findElement(inputArray, value) {
    for(var i=0;i<=inputArray.length-1;i++) {
        if(value === inputArray[i]) {
            return i;
        }
    }
}
Buscar un elemento en un arreglo desordenado
function findElement(inputArray) {
    inputArray.forEach(function(item){
        console.log(item);
    });
}
Imprimir todos los elementos de un arreglo
function findElement(inputArray) {
    inputArray.forEach(function(item){
        console.log(item);
    });
    inputArray.forEach(function(item){
        console.log(item);
    });
}
Esta función es O(2n), pero también se considera como O(n). Veremos la explicación más adelante.
O(n)

O(n)

O(n log n)

Este es frecuentemente aplicado en los algoritmos de tipo Divide and Conquer donde el problema se va dividiendo en piezas mas pequeñas, por ejemplo: Quick Sort, Merge Sort, Heap Sort, etc.

var n = 100
for(var i = 0; i < n; i++) {//this loop is executed n times, so O(n)
    for(var j = n; j > 0; j/=2) {//this loop is executed O(log n) times
    	console.log(n + j);
    }
}
El loop externo se ejecuta n veces y el interior log(n) = n log(n)
O(n log n)

O(n log n)

O(n2)

Comúnmente es asociado con procesos anidados O(n2), O(n3), etc. Por ser un proceso muy costoso,  se recomienda refactorizar si en algún momento llegamos a caer en este tipo de notación.

function printMultiplications(inputArray) {
    inputArray.forEach(function(item1){
	    inputArray.forEach(function(item2){
	        console.log(item1 + 'x' + item2 + '=' + (item1 * item2));
	    });
    });
}

printMultiplications([1,2,3,4,5,6,7,8,9,10])
Imprimir las tablas de multiplicar
O(n2)

O(n2)