¿Qué es la Notación Big O?

¿Qué es la Notación Big O?

La notación Big O es una forma matemática de expresar el rendimiento de un algoritmo.

Por lo tanto, nos indica lo eficiente que es. Y de este modo, lo podemos comparar con otros.

Es una manera de poder expresar de manera abstracta, la capacidad de proceso que tiene un algoritmo. Y nos sirve para determinar si aumentando los valores de entrada, el algoritmo va a ser más o menos rápido.

Vamos a poner números y que esto quede más claro. 😉

• Imagina un algoritmo al que si se le pasa 1 parámetro de entrada, tarda 1 segundo en devolver el resultado de salida
• Si se le pasan 2 parámetros de entrada, tarda 2 segundos en completarse
• Si se le pasan 3 parámetros de entrada, tarda 3 segundos en completarse

Sencillo, ¿verdad?

Pues esto sería una progresión aritmética. ✅

Vayamos ahora con otro algoritmo:

• A este si se le pasa 1 parámetro de entrada, tarda 2 segundos en devolver el resultado de salida.
• Pero… si se le pasan 2 parámetros de entrada, tarda 4 segundos en completarse
• Y si se le pasan 4 parámetros de entrada, tarda 8 segundos en completarse

Esto ya no es lineal, ¿a qué no?

De hecho, se ve claro que la salida es el doble de la entrada.

Pues este algoritmo se correspondería con una progresión geométrica. ✅

Otro ejemplo más:

• A este, si se le pasa 1 parámetro de entrada, tarda 1 segundo en completarse
• Si se le pasan 2 parámetros de entrada, tarda 4 segundos en completarse
• Si se le pasan 3 parámetros de entrada, tarda 9 segundos en completarse

Vemos que la salida es el cuadrado de la entrada.

La curva que se vería en la gráfica que saldría de aquí, sería más pronuncionada aún que la anterior.

Sería una progresión cuadrática. ✅

En el primer caso, la Big O sería O(n).

En el segundo, O(2 * n).

Y en el tercero, O(n2).

Ventajas de la Notación Big O

Lo bueno de la notación Big O es que permite abstraernos de la máquina donde se está ejecutando. Por lo tanto, nos podemos centrar en lo eficiente que es el código en sí.

No queremos que si se corre el programa sobre una máquina más potente, el resultado sea diferente.

No sería no sería un método muy práctico de medida, ¿a qué no? 😊

También puedes solicitar que te revise tus algoritmos.

Valores típicos

Algunos de los valores típicos de la Big O, suelen ser estos:

• O(1) –> Tiempo constante
• O(log n) –> Tiempo logarítmico
• O(n) –> Tiempo lineal
• O(n2) –> Tiempo cuadrático
• O(n!) –> Tiempo factorial

Como habrás podido suponer, están ordenados de más eficiente a menos.

Curiosidad

La O viene de «Order».

Es decir, de clasificar el orden de magnitud de de la función a analizar.

Y como otra curiosidad, comentarte que en la membresía, tenemos un canal de retos, donde puedes proponer algoritmos que implementar en Kotlin.