Notación Big-O

Introducción

Esto es un concepto sumamente importante, Big-O es el lenguaje que usamos para identificar la eficiencia de un algoritmo. Es fundamental que lo comprendas a fondo ya que te ayudara a entender que tan lento o rápido corren tus algoritmos.

Recordemos que un algoritmo es un conjunto de instrucciones o reglas - ordenadas y definidas que típicamente permite solucionar un problema, realizar computaciones, procesar datos, etc.

Te lo intentare explicar con una analogía. Imagínate que mi sobrina Ariana que colecciona estampas, que por ahora esta empezando - tiene una colección de 100 estampas. Ella esta intentando elegir entre qué algoritmo es mejor para buscar la estampa que ella quiere - Simple Search o Binary Search. Cada algoritmo tiene sus pros y contras.

Simple Search es más fácil de escribir y menos proclive a bugs, pero el algoritmo tarda 1 segundo por cada estampa que tiene que buscar = 100 segundos. Por el otro lado Binary Search es mas rápido Log2(100) = 7segundos (no te preocupes por las matemáticas por ahora).

Puedes encontrar explicaciones simples en paginas como estas . Solo Recuerda que cuando decimos que Log2(8) = 3, esto quiere decir que necesitamos multiplicar 2 (la base) 3 veces para llegar a 8.

Nota: no es importante que sepas logaritmos en profundidad, pero sí sirve tener cierta noción de cómo funcionan - Video .

Por ahora sabemos que 100 segundos no es mucho problema cuando buscamos una estampa en especifico, pero que pasaría si la colección de Ariana creciera a 1 millón de estampas? El algoritmo de Simple Search tardaría 1,000,000 segundos - el equivalente a más de 11 días. Mientras que Binary Search tardaría 20 segundos en encontrar la estampa. Con esto podemos ver que los algoritmos se escalan significativamente conforme crece la cantidad de operaciones. También es importante darse cuenta que Big-O denota el peor caso posible de nuestro algoritmo, ya que también seria posible que encontráramos la estaba en la operación numero 3 si tuviéramos suerte, pero este concepto no es util al momento de definir si un algoritmo es eficiente.

Entonces podríamos definir que nuestro Simple Search se define como O(N). O -> diciendo que nos referimos a Big-O y N al numero de operaciones necesarias. En el caso de 100 estampas el Big-O de Simple Search seria de O(100).

Los tipos mas comunes de Big-O

Están ordenadas de la mas rapida a la mas lenta
N se refiere al numero de operaciones
Es muy poco probable que necesites saber mas de estos para entrevistas

O(1) Constant Runtime

O(log N) - Logaritmic Runtime

O(N) - Linear Runtime

O(N * log N) - Linearithmic Runtime

O(N ˆ 2) - Quadratic Runtime

O(2 ˆ N) - Exponential Runtime

O(N!) - Factorial Runtime

imagen

Es importante notar que la eficiencia de un algoritmo no se mide en segundos. Se mide en el incremento en cantidad de operaciones necesarias.

Visualizemos diferentes tipos de Big-O

O(N) - Linear Runtime

Este quiere decir que la cantidad de operaciones necesarias sera igual que el numero de elementos que tengamos que iterar. Imagínate este código que encuentra el menor y mayor valor en un array en este tiempo O(N):

int[] intArray = {1,5,10,20,2,6,12};
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;

for (int x : intArray) {
    if (x < min ) min = x;
    if (x > max) max = x;
}

Nota: Es importante notar que en el caso dé Big-O notation intentaremos obviar otras constantes como O (2N), O(N * 2) etc. Ya que no es de importancia para nosotros por razones que prefiero no explicar aquí - ya que podríamos ir hasta assembly code para desaprobar este tema. Aquí lo explico con un ejemplo:

int[] intArray = {1,5,10,20,2,6,12};
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;

for (int x : intArray) {
    if (x < min ) min = x;
}
for (int x : intArray) {
    if (x > max) max = x;
}

En este caso aunque iteremos dos veces, siempre es sobre el mismo array - muchas personas pensarían que se expresaría cómo O(2N) o cómo O(N * 2), pero en verdad se escribe como O(N).

Ejemplos

Atravesando un array
Atravesando una linked list
Búsqueda lineal (Simple Search)
Comparando dos Strings
Eliminando un elemento de una Linked List (No ordenada)
Encontrando un Palindromo

Algoritmos de multiples partes (suma y multiplicación)

Una fuente de confusion constante es cuando tenemos multiples sets de datos con las cuales haremos operaciones. Estos casos se cubren con suma y multiplicación.

Suma

La suma es muy simple, se obtiene cuando tenemos dos estructuras de datos separadas. Este ejemplo se escribiría de la siguiente forma O(A + B)

int[] arrayA = {1,5,10,20,2,6,12};
int[] arrayB = {100,200,300,400,500,600};

for (int x : arrayA) {
    if (x < min ) min = x;
}
for (int x : arrayB) {
    if (x > max) max = x;
}

Multiplicación

Para obtener la multiplicación tendriamos que hacer operaciones en la estructura de datos B dentro de la estructura de datos A. Este ejemplo se escribiría de la siguiente forma O(A * B)

int[] arrayA = {1,5,10,20,2,6,12};
int[] arrayB = {100,200,300,400,500,600};

for (int x : arrayA) {
    for (int y : arrayB) {
        System.out.println(x + y);
    }
}

O(1) - Constant Runtime

Este se refiere a que la cantidad de operaciones siempre sera la misma y es la mas rápida posible:

int returnFirst(int[] array) {
    return array[0];
}

Ejemplos

Acezando un array por su indice
insertando un node dentro de una Linked List
Pushing/popping de un stack
insertando/removiendo de una queue (cola)

O(Log N) - Logarithmic Runtime

Como hemos hablado al principio, el ejemplo mas claro de esto es ver Binary Search. Esto se refiere cuando recurrentemente dividimos la cantidad de operaciones necesarias dentro de 2. Veamos este ejemplo:

int[] array = {0,1,2,3,4,5,6,7,8,9,10}; // Array ordenada

Si Binary Search quisiera encontrar el numero 9 - empezaría encontrando el numero de en medio como pivote - en este caso el numero 5. Ya sabiendo que la array esta ordenada sabe que para llegar a 8 tiene que ser > 5. Entonces decide solo ver los números restantes al lado derecho del Array.

int[] array = {6,7,8,9,10} // Array restante

De nuevo se obtiene el numero de en medio como pivote - en este caso el 8. Sabemos que 9 > 8 así que decidimos volver a ver en el resto de los elementos en el array al lado derecho del pivote: {9,10}. En la siguiente operación ya solo tendremos 2 elementos y sabremos que uno de esos dos es el que estamos buscando.

int[] array = {9, 10} // array restante

Cómo puedes ver después de cada operación N se reduce a la mitad -> N/2 -> N/4 -> N/8, etc. Esto puede que pase hasta que N se convierta en 1 en el peor de los casos. La clave aquí es saber identificar qué típicamente cuando miramos que una solución sigue reduciendo la cantidad de operaciones a la mitad, nos referiremos a O(Log N).

Ejemplos

Búsqueda binaria
Encontrando el mayor/menor numero en un Binary Search Tree

O(N^2) - Quadratic runtime

Cuadratica se refiere cuando el peor tiempo posible es directamente proporcional al tamaño de la estructura de datos al cuadrado.

for (let x: array) {
    for (let y: array) {
        System.out.println(x + y);
    }
}

Ejemplos

Bubble Sort
Insertion Sort
Selection Sort
Atravesando un array de 2D

O(N log N) - Linearithmic runtime

Linearitmica se refiere cuando corremos una operación logarítmica N(Log N) una cantidad N de veces. La mayoría de sorting algorithms son así. Estos son bastante largos para explicar aquí, pero en la parte de algoritmos desarrollare este tipo de problemas después.

Ejemplos

Merge Sort
Heap Sort
Quick Sort

O(2 ^ N) - Exponential runtime

Este ocurre cuando por cada incremento en el tamaño de la estructura de datos - el runtime se duplica. Para un set de datos pequeños este algoritmo no parecerá como mucho, pero conforme el set de datos incremente el runtime incrementa drásticamente. Un ejemplo es una solución recursiva para encontrar Fibonacci.

int fibonacci(int n) {
    if (n <= 1) return 1;
    return fibonacci(n - 2 ) + fibonacci(n - 1);
}

O(N!) - Factorial runtime

Este es el peor de los casos. Por ejemplo un algoritmo que busque cada posible permutación en una estructura de datos sera N!

Algoritmos recursivos

Veamos el siguiente algoritmo recursivo:

int f(intn) {
    if(n == 1) return1;
    returnf(n - 1) + f(n - 1);
}

Muchísimos programadores pensarían de que esto se resuelve de cierta forma logarítmica, pero para esto existe una formula muy fácil, es ramas elevado a la profundidad - O(Ramas ^ Profunidad). Ahora te lo explico, imaginémonos que con este simple algoritmo recursivo introducimos el numero 4, ocurriría algo como esto:

imagen

Aquí podemos ver de que cuando llamamos la función con el numero 4 en verdad se generan 4 grados de profundidad, ya que el algoritmos tiene “2 ramas” y con esto me refiero a la cantidad de veces que se llama la función recursivamente a si misma. Con esto podemos derivar que en este caso el tiempo para este algoritmo seria de O(2 ^ N).