Notacion Big O

Hoy vamos a hablar sobre un tema muy importante a la hora de programar y hacer nuestro código eficiente. En programación para detectar la eficiencia de un algoritmo utilizamos lo que se llama notación big O (big O notation en inglés) .

En el mundo laboral o el día a día probablemente no sea tan importante pero desde luego en la gran mayoría de entrevistas y en las entrevistas para “FAANG” es crucial tener claro este concepto. 

1 - Qué es la notación big O?

La notación big O es un sistema que nos permite comparar dos algoritmos. Entendiendo la notación seremos capaces de analizar el mejor de los escenarios, cuando tengamos múltiples opciones para poder elegir el más efectivo y el que va a funcionar mejor cuando tengamos una carga elevada.

Cuando definimos la eficiencia de un algoritmo no lo hacemos indicando el número de pasos como tal como podría ser “un algoritmo de 200 pasos y otro de 120 pasos”. Esto es debido a que el número de pasos no puede ser reducido a un número para todos los casos. 

Por ejemplo, si utilizamos un algoritmo de búsqueda lineal (osea comprueba cada elemento de una lista uno por uno) ese mismo algoritmo tarda 200 pasos para un array de 200 elementos y 120 para un array de 120 elementos en el peor de los escenarios. 

Para simplificar y mejorar la comunicación hablando de la complejidad de los algoritmos utilizamos un concepto de las matemáticas llamado “notación Big O”, para este post no hace falta saber de matemáticas ya que voy a reducir los conceptos matemáticos lo máximo posible. 

Una vez entendemos como la notación big O funciona analizar algoritmos es mucho más sencillo, lo que siempre puede ayudarte a la hora de escribir código y por supuesto a la hora de revisar el de tus compañeros.

2 - Cómo calcular la eficiencia de un algoritmo con Big O

Cuando calculamos la eficiencia de un algoritmo Big O lo hacemos centrándonos en el número de pasos, pero lo hacemos de una forma especial.

2.1 - Qué significa O(N) en notación Big O?

Por ejemplo en el caso anterior, hemos dicho que en una búsqueda lineal en un array con 200 elementos puede llegar a tardar 200 pasos mientras que si son 400 elementos serán 400 pasos. 

Esto quiere decir que para el algoritmo de búsqueda lineal va a tener tantos pasos como elementos. Si convertimos esta información a las matemáticas, nos daremos cuenta que la “complejidad = n”, donde “n” es el número de elementos. 

En la terminología Big o esto se expresa “O(N)”, lo que además quiere decir que ese algoritmo va a tener un tiempo de ejecución lineal, si introduces 10 elementos, tardará 10 pasos, mientras que si introduces 100 tardará 100 pasos.

Por lo tanto, como podemos ver en la imagen, ambos procesos están en la categoría O(N) pese a uno tener un paso extra. Ya que cuando definimos big O lo hacemos de forma relativa a sus datos de entrada.

Podemos decir, que O(N) tiene un número de pasos proporcional al número de elementos de entrada.

2.2 - Qué significa O(1) en notación Big O?

con la información anterior podemos deducir que O(1) es un único paso, y podemos ver este resultado cuando accedemos por índice a un array, ya que un array asigna la memoria física del ordenador de forma consecutiva cuando es instanciado.

Por ejemplo un array de 6 elementos, que su primera dirección de memoria es la 2222 la segunda será siempre 2223  (2222 + 1) por lo que haciendo array[1] únicamente necesitamos un paso para obtener el resultado.

Por lo tanto podemos comparar ambos tipos de algoritmo en un gráfico:

2.3 - Qué significa O(log n) en notación Big O?

Acabamos de ver que O(1) se utiliza cuando es un solo paso, y O(N) cuando es el mismo número de pasos que elementos de entrada.

Pero estos no son los únicos tipos, por ejemplo si tenemos un array de enteros ordenados y queremos buscar un número, tenemos dos opciones, o buscamos uno por uno utilizando una búsqueda lineal, o por el contrario podemos hacer una búsqueda binaria donde, comparamos el elemento del medio si es mayor o menor y sobre ese subgrupo volvemos a comprar.

Debemos repetir el proceso hasta que encontremos el resultado.

En este ejemplo, como podemos observar utilizando la búsqueda binaria únicamente tardamos dos pasos, mientras que en la búsqueda lineal tardaríamos 5.

Esto se debe a que cada vez vamos dividiendo por 2 el número de elementos que vamos a comprobar.

Por ejemplo una búsqueda binaria con 100 elementos tarda en el peor de los casos 7 pasos, mientras que una búsqueda lineal tardaría 100.

2.3.1 - Qué son los Logaritmos?

Antes de continuar simplemente un pequeño detalle, este punto es debido a que “log” es una abreviación de logaritmo.

Los logaritmos son la parte inversa a los componentes, como recordamos un componente es “elevar” por ejemplo 23 se traduce en 2*2*2 con el resultado de 8.

Por lo que lo opuesto sería un logaritmo que es cuantas veces tienes que dividir el número por 2 hasta que obtienes 1. 8/2/2/2 = 1 lo que se traduce en log2 8 = 3.

Nota: cuando indicamos la notación big O quitamos el pequeño 2 ya que sería repetición innecesaria.

2.4 - Qué significa O(N²) en notación Big O

Cuando calculamos big O siempre lo hacemos en función de los parámetros de entrada, hasta ahora hemos visto O(1) cuando es un único paso, O(N) cuando son tantos pasos como elementos y O(log n) vamos dividiendo el número de elementos a cada paso.

Pero existe la posibilidad inversa, en vez de reducirse se doble, por ejemplo en un algoritmo de bubble sort. 

En el algoritmo bubble sort comparamos el primer elemento con el segundo, y si el primero es mayor los intercambiamos, debemos hacer este proceso tantas veces como elementos tenga el array, y lo hacemos sobre el array entero.

A efectos de programación es un bucle for dentro de otro.

Este tipo de algoritmo destaca por ser mucho más lento que O(N), y además tiene un nombre especial, algoritmo cuadrático. 

Nota: en caso de tener 3 bucles anidados sería o(n3) como puedes observar se puede ampliar todo lo que sea necesario. Pero a cada exponente que añadimos será más y más lento. Al que llamamos algoritmo cúbico.

2.5 - Múltiples set de datos en notación big o

Cuando construimos algoritmos no siempre tienen únicamente un array de entrada, sino que muchas veces pueden ser dos o incluso más.

También podemos medir estos casos, para el caso de dos arrays de entrada sería O(N*M) pero en una gráfica no sabemos cómo dibujar, simplemente en algún punto entre O(N) y O(N2) a sabiendas de que si ambos  arrays tienen el mismo tamaño sería O(N2).

Lo mismo aplicaría si tuviéramos 3, sabríamos que en el gráfico está en algún punto entre O(N) y O(N^3)

3 - Subgrupos dentro del mismo tipo de algoritmo

Elegir la notación big O es importante, ya que nos agrupa diferentes algoritmos en grupos. Pero ahí no acaba la cosa, hay que tener en cuenta que no todos los algoritmos en la categoría tienen que ser exactamente iguales.

He indicado anteriormente en el caso de los logaritmos que realmente son log₂ pero que quitamos el dos.

Bueno pues lo mismo sucede cuando tenemos un algoritmo que tarda la mitad de n, podríamos representarlo O(N/2) o uno que tarda el doble O(2N) en ambos removemos el dos (o el número que sea) por simplicidad, lo que hace que ambos algoritmos caigan sobre el mismo grupo O(N).

Este apartado lo podemos ver más facil con dos algoritmos “selectionSort” e “insertionSort”

El primero responde a un algoritmo de O(N2) pero en realidad es O(N2/2):

public static int[] SelectionSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int lowestNumberIndex = i;
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[j] < array[lowestNumberIndex])
            {
                lowestNumberIndex = j;
            }
        }
        if (lowestNumberIndex != i)
        {
            int temporal = array[i];
            array[i] = array[lowestNumberIndex];
            array[lowestNumberIndex] = temporal;
        }
    }
    return array;
}

Mientras que el segundo, también es un algoritmo O(N2) pero en realidad es O(N2 +N).

public static int[] InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int valueToCompare = array[i];
        for (int k = i-1; k >= 0; k--)
        {
            if (array[k] > valueToCompare)
            {
                array[k+1] = array[k];
            }
            else
            {
                break;
            }
            array[k] = valueToCompare;
        }
    }
    return array;
}

Esta característica hace que podamos identificar de una manera muy rápida que tipo de algoritmo estamos viendo, pero en caso de tener más de una opción dentro de la misma categoría debemos invertir tiempo en ver en detalle exactamente cómo funciona el algoritmo por dentro.  

3.1 - Cómo identificar Big O en el código

Para saber el grupo o categoría principal en el que está un algoritmo debemos fijarnos en dos aspectos importantes.

1 - En el número de elementos de entrada

Así identificamos si es O(n), o(n*m) etc.

2 - En el número de bucles que hacen referencia al elemento de entrada

Para introducirlo en una categoría no tenemos en cuenta las operaciones aritméticas que contiene, sino que nos centraremos únicamente en los bucles que hacen referencia al elemento de entrada.

Por ejemplo, si tienes un bucle que imprime “hola” 10 veces por cada elemento de entrada, no debemos tenerlo en cuenta para su notación big O, ya que es un elemento estático que nunca cambia.

Conclusión

• En este post hemos visto qué es la notación big o así como algunos de sus diferentes tipos.
• Hemos visto cómo identificar notación big o en el código.
• Personalmente indicar que si bien en el día a día no es tan importante en las entrevistas de trabajo si lo es. 
• Por supuesto en algunos casos donde tenemos que hacer código muy depurado para sostener grandes cargas, entender la notación big O nos ayudará a entender mejor el fljo del código y por ende, el tiempo o la carga que sostendrá.