¿Qué es la notación Big-O?

¿Alguna vez te has preguntado por qué un programa que escribiste tardó tanto en ejecutarse? Quizás le gustaría saber si puede hacer que su código sea más eficiente. Comprender cómo se ejecuta el código puede llevarlo al siguiente nivel. La notación Big-O es una herramienta útil para calcular qué tan eficiente es realmente su código.

¿Qué es la notación Big-O?

La notación Big-O le brinda una forma de calcular cuánto tiempo llevará ejecutar su código. Puede medir físicamente cuánto tarda su código en ejecutarse, pero con ese método es difícil detectar pequeñas diferencias de tiempo. Por ejemplo, el tiempo que tarda entre ejecutar 20 y 50 líneas de código es muy pequeño. Sin embargo, en un programa grande, esas ineficiencias pueden acumularse.

La notación Big-O cuenta cuántos pasos debe ejecutar un algoritmo para medir su eficiencia. Acercarse a su código de esta manera puede ser muy efectivo si necesita ajustar su código para aumentar la eficiencia. La notación Big-O le permitirá medir diferentes algoritmos por la cantidad de pasos que requiere para ejecutar y comparar objetivamente la eficiencia de los algoritmos.

¿Cómo se calcula la notación Big-O?

Consideremos dos funciones que cuentan cuántos calcetines individuales hay en un cajón. Cada función toma el número de pares de calcetines y devuelve el número de calcetines individuales. El código está escrito en Python, pero eso no afecta la forma en que contamos el número de pasos.

Algoritmo 1:

 def sockCounter(numberOfPairs):
 individualSocks = 0
 for x in range(numberOfPairs):
 individualSocks = individualSocks + 2
 return individualSocks

Algoritmo 2:

 def sockCounter(numberOfPairs):
 return numberOfPairs * 2

Este es un ejemplo tonto, y debería poder decir fácilmente qué algoritmo es más eficiente. Pero para practicar, repasemos cada uno.

RELACIONADO: ¿Qué es una función en la programación?

El algoritmo 1 tiene muchos pasos:

1. Asigna un valor de cero a la variable individualSocks.
2. Asigna un valor de uno a la variable i.
3. Compara el valor de i con numberOfPairs.
4. Agrega dos a individualSocks.
5. Se asigna a sí mismo el valor aumentado de individualSocks.
6. Incrementa i en uno.
7. Luego repite los pasos 3 a 6 el mismo número de veces que (calcetines individuales – 1).

El número de pasos que tenemos que completar para el algoritmo uno se puede expresar como:

 4n + 2

Hay cuatro pasos que tenemos que completar n veces. En este caso, n sería igual al valor de numberOfPairs. También hay 2 pasos que se completan una vez.

En comparación, el algoritmo 2 solo tiene un paso. El valor de numberOfPairs se multiplica por dos. Expresaríamos eso como:

 1

Si aún no era evidente, ahora podemos ver fácilmente que el algoritmo 2 es bastante más eficiente.

Análisis Big-O

Generalmente, cuando está interesado en la notación Big-O de un algoritmo, está más interesado en la eficiencia general y menos en el análisis de grano fino del número de pasos. Para simplificar la notación, podemos simplemente indicar la magnitud de la eficiencia.

En los ejemplos anteriores, el algoritmo 2 se expresaría como uno:

 O(1)

Pero el algoritmo 1 se simplificaría como:

 O(n)

Esta instantánea rápida nos dice cómo la eficiencia del algoritmo uno está ligada al valor de n. Cuanto mayor sea el número, más pasos deberá completar el algoritmo.

Código lineal

Debido a que no conocemos el valor de n, es más útil pensar en cómo el valor de n afecta la cantidad de código que debe ejecutarse. En el algoritmo 1 podemos decir que la relación es lineal. Si traza el número de pasos frente al valor de n, obtiene una línea recta que sube.

Código cuadrático

No todas las relaciones son tan simples como el ejemplo lineal. Imagine que tiene una matriz 2D y le gustaría buscar un valor en la matriz. Puede crear un algoritmo como este:

 def searchForValue(targetValue, arraySearched):
 foundTarget = False
 for x in arraySearched:
 for y in x:
 if(y == targetValue):
 foundTarget = True
 return foundTarget

En este ejemplo, el número de pasos depende del número de matrices en arraySearched y del número de valores en cada matriz. Entonces, el número simplificado de pasos sería n * no n².

Esta relación es una relación cuadrática, lo que significa que el número de pasos en nuestro algoritmo crece exponencialmente con n. En notación Big-O, lo escribiría como:

 O(n²)

RELACIONADO: Herramientas útiles para verificar, limpiar y optimizar archivos CSS

Código logarítmico

Aunque hay muchas otras relaciones, la última relación que veremos son las relaciones logarítmicas. Para refrescar su memoria, el registro de un número es el valor del exponente requerido para alcanzar un número dada una base. Por ejemplo:

 log 2 (8) = 3

El logaritmo es igual a tres porque si nuestra base fuera 2, necesitaríamos un valor de exponente de 3 para llegar al número 8.

Entonces, la relación de una función logarítmica es lo opuesto a una relación exponencial. A medida que aumenta n, se requieren menos pasos nuevos para ejecutar el algoritmo.

A primera vista, esto parece contrario a la intuición. ¿Cómo pueden los pasos de un algoritmo crecer más lentamente que n? Un buen ejemplo de esto son las búsquedas binarias. Consideremos un algoritmo para buscar un número en una matriz de valores únicos.

• Comenzaremos con una matriz para buscar en orden de menor a mayor.
• A continuación, comprobaremos el valor en el medio de la matriz.
• Si su número es más alto, excluiremos los números más bajos en nuestra búsqueda y si el número fue más bajo, excluiremos los números más altos.
• Ahora, veremos el número medio de los números restantes.
• Nuevamente, excluiremos la mitad de los números en función de si nuestro valor objetivo es mayor o menor que el valor medio.
• Continuaremos este proceso hasta que encontremos nuestro objetivo o determinemos que no está en la lista.

Como puede ver, dado que las búsquedas binarias eliminan la mitad de los valores posibles en cada pasada, a medida que n aumenta, el efecto sobre la cantidad de veces que verificamos la matriz apenas se ve afectado. Para expresar esto en notación Big-O, escribiríamos:

 O(log(n))

La importancia de la notación Big-O

Big-O nation le brinda una manera rápida y fácil de comunicar cuán eficiente es un algoritmo. Esto hace que sea más fácil decidir entre diferentes algoritmos. Esto puede ser particularmente útil si está utilizando un algoritmo de una biblioteca y no necesariamente sabe cómo se ve el código.

Cuando aprende a codificar por primera vez, comienza con funciones lineales. Como puede ver en el gráfico anterior, eso lo llevará muy lejos. Pero a medida que adquiere más experiencia y comienza a crear código más complejo, la eficiencia comienza a convertirse en un problema. La comprensión de cómo cuantificar la eficiencia de su código le brindará las herramientas que necesita para comenzar a ajustarlo para lograr eficiencia y sopesar los pros y los contras de los algoritmos.