Notación Big O

Primero tenemos que reforzar y entender el concepto de función. Una función se dedica a transformar una entrada en una salida.

Supongamos que tenemos el número 3, digamos que queremos sumarle 1 a nuestro numero 3, y el resultado lo pondremos en una variable, llamémosla “y”.

Podríamos decir que:

y = 3 + 1

Sin embargo, digamos que ahora queremos sumarle 1 a cualquier número (no solo a 3), por lo que en lugar de escribir 3, escribimos x. Nuestra fórmula sería:

y = x+1

Ahora para cada numero de entrada (x) podemos tener una salida (x+1).

Ese “x+1” lo guardamos en una variable , pero también podríamos representarlo de la siguiente manera:

f(x) = x+1

En español significa : “La transformación de x es igual a x+1”.

Si quisiéramos usar nuestra función (x+1) para transformar los números del 1 al 5 podríamos tabular nuestros resultados de la siguiente forma:

+---+------+
| x | f(x) |
+---+------+
| 1 | 2 |
+---+------+
| 2 | 3 |
+---+------+
| 3 | 4 |
+---+------+
| 4 | 5 |
+---+------+
| 5 | 6 |
+---+------+

Y no es todo, podemos graficar esa función en un mapa cartesiano:


Ahora que hemos visto que a partir de una función de entrada se puede sacar una tabulación y una gráfica (de cualquier función), vamos a proceder a estudiar funciones más interesantes.


Digamos que queremos obtener el último elemento de un arreglo. Podemos hacerlo de 2 formas:

  1. Acceder directamente al elemento:
var arreglo = [1,2,3,4]
arreglo[arreglo.length -1]
// regresa 4

2. Recorrer el arreglo de principio a fin y retornar solo el último valor:

var arreglo = [1,2,3,4]
for(var i = 0;i < arreglo.length; i ++){
if (i = arreglo.length-1){
return arreglo[i]
}
}

A pesar que ambas scripts hacen los mismo, es importante notar que el primero sólo hace 1 operación y el segundo hace 4.

Curiosamente el número de elementos de entrada también es 4. (arreglo.length)

Si tuviéramos un arreglo de 20 elementos y volviéramos a correr el segundo ejemplo, ahora tendríamos que ejecutar 20 operaciones.

Pero ya quiero saber qué es Big O…

A grandes rasgos, es la cantidad de operaciones que se van a ejecutar en nuestro algoritmo y la mayoría de las veces, es directamente proporcional al número de datos de entrada en el algoritmo en sí.

Se escribe: O(numeroDeElementosDeEntrada).

Para nuestro primer ejemplo

var arreglo = [1,2,3,4]
arreglo[arreglo.length -1]
// regresa 4

Solo tenemos que hacer una operación, por lo cual O(1) para el segundo ejemplo:

var arreglo = [1,2,3,4]
for(var i = 0;i < arreglo.length; i ++){
if (i = arreglo.length-1){
return arreglo[i]
}
}

Se hacen tantas operaciones como elementos de entrada tengamos. (Si tenemos 20 elementos en el arreglo, tenemos que preguntar 20 veces si es el último número), por lo que este algoritmo corre en O(número de elementos de entrada), pero como es muy largo de escribir “número de elementos de entrada”, llamémoslos N.

Por lo que el segundo algoritmo, corre en O(N)

Ahora, analicemos un for anidado (de esos que se usan para recorrer matrices):

var matriz = [[1,2],[7,6],[4,7]]
for(var i = 0; i< matriz.length; i++){
    for(var k=0;k < matriz[i].length;k++){
console.log(k)
    }
    console.log(i)
}

Se considera como operación cada vez que se muestra i o k, así, podemos ver que se muestran 9 números:

Curiosamente la entrada es 3, y sabemos que 3 al cuadrado es 9, por lo que podemos decir que ese algoritmo es O(n ^ 2).


Ya que vimos que la complejidad de ejecución de nuestros algoritmos se incrementa en base al tamaño de entrada de nuestro arreglo y en base al algoritmo implementado. Analicemos una tabla de los tiempos de ejecuciones mas comunes:

Imagen sacada de http://bigocheatsheet.com/

Como podemos ver, escribir algoritmos en O(n ^ 2) (que es el tiempo de ejecución del Ordenamiento Burbuja) puede ser increíblemente costoso, mientras se incrementa el tamaño de la muestra. (Ver como aumenta el costo de las operaciones necesarias para realizarse).

Por otro lado, O(n log2 n) (tiempo de ejecución de Mergesort), ya no escala tanto en tiempo de ejecución, si incrementa el tamaño de la muestra.


De regalo te dejo una tabla donde vienen los tiempos de ejecución y acceso de algunos algoritmos de ordenamiento y estructuras de datos:

http://bigocheatsheet.com/

Show your support

Clapping shows how much you appreciated Emmanuel Orozco’s story.