Big O Notation

¿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. [pastacode lang="javascript" manual="function%20printFirstItem(allItems)%20%7B%0A%20%20return%20allItems%5B0%5D%3B%0A%7D" message="Búsqueda de un elemento usando un índice" highlight="" provider="manual"/] [caption id="attachment_7256" align="aligncenter" width="800"]O(1) O(1)[/caption]

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. [pastacode lang="javascript" manual="function%20binarySearch%20(list%2C%20value)%20%7B%0A%20%20%20%20let%20start%20%3D%200%0A%20%20%20%20let%20stop%20%3D%20list.length%20-%201%0A%20%20%20%20let%20middle%20%3D%20Math.floor((start%20%2B%20stop)%20%2F%202)%0A%0A%20%20%20%20while%20(list%5Bmiddle%5D%20!%3D%3D%20value%20%26%26%20start%20%3C%20stop)%20%7B%0A%20%20%20%20%20%20%20%20if%20(value%20%3C%20list%5Bmiddle%5D)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20stop%20%3D%20middle%20-%201%0A%20%20%20%20%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20middle%20%2B%201%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20middle%20%3D%20Math.floor((start%20%2B%20stop)%20%2F%202)%0A%20%20%20%20%7D%0A%20%20%20%20return%20(list%5Bmiddle%5D%20!%3D%3D%20value)%20%3F%20-1%20%3A%20middle%0A%7D%0A" message="Búsqueda binaria" highlight="" provider="manual"/] [caption id="attachment_7248" align="aligncenter" width="800"]O(log n) O(log n)[/caption]

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. [pastacode lang="javascript" manual="function%20findElement(inputArray%2C%20value)%20%7B%0A%20%20%20%20for(var%20i%3D0%3Bi%3C%3DinputArray.length-1%3Bi%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20if(value%20%3D%3D%3D%20inputArray%5Bi%5D)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A" message="Buscar un elemento en un arreglo desordenado" highlight="" provider="manual"/] [pastacode lang="javascript" manual="function%20findElement(inputArray)%20%7B%0A%20%20%20%20inputArray.forEach(function(item)%7B%0A%20%20%20%20%20%20%20%20console.log(item)%3B%0A%20%20%20%20%7D)%3B%0A%7D%0A" message="Imprimir todos los elementos de un arreglo" highlight="" provider="manual"/] [pastacode lang="javascript" manual="function%20findElement(inputArray)%20%7B%0A%20%20%20%20inputArray.forEach(function(item)%7B%0A%20%20%20%20%20%20%20%20console.log(item)%3B%0A%20%20%20%20%7D)%3B%0A%20%20%20%20inputArray.forEach(function(item)%7B%0A%20%20%20%20%20%20%20%20console.log(item)%3B%0A%20%20%20%20%7D)%3B%0A%7D%0A" message="Esta función es O(2n), pero también se considera como O(n). Veremos la explicación más adelante." highlight="" provider="manual"/] [caption id="attachment_7253" align="aligncenter" width="800"]O(n) O(n)[/caption]

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. [pastacode lang="javascript" manual="var%20n%20%3D%20100%0Afor(var%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%20%7B%2F%2Fthis%20loop%20is%20executed%20n%20times%2C%20so%20O(n)%0A%20%20%20%20for(var%20j%20%3D%20n%3B%20j%20%3E%200%3B%20j%2F%3D2)%20%7B%2F%2Fthis%20loop%20is%20executed%20O(log%20n)%20times%0A%20%20%20%20%09console.log(n%20%2B%20j)%3B%0A%20%20%20%20%7D%0A%7D" message="El loop externo se ejecuta n veces y el interior log(n) = n log(n)" highlight="" provider="manual"/] [caption id="attachment_7257" align="aligncenter" width="800"]O(n log n) O(n log n)[/caption]

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. [pastacode lang="javascript" manual="function%20printMultiplications(inputArray)%20%7B%0A%20%20%20%20inputArray.forEach(function(item1)%7B%0A%09%20%20%20%20inputArray.forEach(function(item2)%7B%0A%09%20%20%20%20%20%20%20%20console.log(item1%20%2B%20'x'%20%2B%20item2%20%2B%20'%3D'%20%2B%20(item1%20*%20item2))%3B%0A%09%20%20%20%20%7D)%3B%0A%20%20%20%20%7D)%3B%0A%7D%0A%0AprintMultiplications(%5B1%2C2%2C3%2C4%2C5%2C6%2C7%2C8%2C9%2C10%5D)" message="Imprimir las tablas de multiplicar" highlight="" provider="manual"/] [caption id="attachment_7281" align="aligncenter" width="800"]O(n2) O(n2)[/caption]
Note to VCs: Aviada is not for sale. Please look somewhere else.