Gran O para principiantes

Foto de apoorv mittal en Unsplash

La notación Big O nos permite medir la complejidad temporal y espacial de nuestro código.

Piensa en el ejemplo de un bucle for. Puede ejecutarlo en una matriz de 5 elementos y se ejecutará bastante rápido, pero si lo ejecutó en una matriz de 10,000 elementos, el tiempo de ejecución será mucho más lento. Vea un ejemplo:

La notación Big O nos permite calcular cuánto tardará en ejecutarse un algoritmo. Esto nos permite entender cómo se escalará una pieza de código. Mide la eficiencia algorítmica.

O(1)

Esto se conoce como tiempo constante. El tiempo es consistente para cada ejecución. Imagínate si fueras un empleado de una gasolinera. Le toma exactamente 25 segundos llenar un automóvil, y luego esa tarea en particular se considera completa. No importa si llena un auto o cien autos ese día, ha llenado el auto en una cantidad constante de tiempo.

Entonces, según nuestro ejemplo anterior, no nos importa O(1), O(2), etc. Lo redondeamos a O(1), lo que quiere decir que nuestra operación es una línea plana en términos de escalabilidad. Tomará la misma cantidad de tiempo. Esto es predecible y muy escalable. Vea un ejemplo:

En)

Nuestro ejemplo de bucle es O(n), ya que se ejecuta para cada valor de nuestra entrada. Las operaciones aumentan de forma lineal según las entradas. (n) representa el número de entradas. El algoritmo se ejecuta en tiempo lineal.

O(n²)

Digamos que queremos registrar una serie de pares de una serie de elementos. Podemos hacerlo así:

Una buena regla general es que si ve bucles anidados, utilice la multiplicación para calcular la notación. Entonces, en nuestro ejemplo anterior, estamos haciendo O(n *n) que se convierte en O(n²) (O de n al cuadrado). Esto se conoce como tiempo cuadrático, lo que significa que cada vez que aumenta el número de elementos, aumentamos las operaciones cuadráticamente.

En realidad, desea evitar el código que se ejecuta en O (n²) ya que la cantidad de operaciones aumenta significativamente cuando introduce más elementos.

Cálculo de O grande

Para calcular Big O, puede revisar cada línea de código y establecer si es O (1), O (n), etc. y luego devolver su cálculo al final. Por ejemplo, puede ser O(4 + 5n) donde el 4 representa cuatro instancias de O(1) y 5n representa cinco instancias de O(n).

Sin embargo, hay una manera más fácil de calcular esto, y se hace con las siguientes cuatro reglas:

1. Asumir lo peor
2. Eliminar constantes
3. Use diferentes términos para las entradas
4. Eliminar cualquier no dominante

Tomando cada uno de estos a su vez:

1. Asumir lo peor

Al calcular Big O, siempre piensas en el peor de los casos. Por ejemplo, si tuviera que recorrer una matriz y buscar un elemento, podría ser el primer elemento o podría ser el último. Como no estamos seguros, debemos asumir O(n) en este caso.

2. Eliminar constantes

Esto es un poco más complicado, pero tengan paciencia conmigo. Considere este código:

Tenemos una función que hace varias cosas. Algunos son O(1) como la línea 3, mientras que otros son O(n) como la línea 9.

Podríamos expresar la notación Big O de esto como O(1 + n/2 +100) pero en realidad es demasiado específica. Podemos eliminar nuestras operaciones O(1) porque, como regla general, es probable que sean insignificantes en comparación con nuestras operaciones O(n). Si proporcionamos un millón de elementos en nuestra matriz de entrada, entonces 100 operaciones adicionales de O(1) no son nuestra principal preocupación.

Entonces tenemos O(n / 2) — a medida que n se hace más y más grande, dividirlo por dos tiene un efecto decreciente. Entonces, en última instancia, nuestra notación Big O para esta función se convierte en O (n).

3. Diferentes términos para las entradas

Si tuviéramos que hacer un bucle dos veces de la misma matriz, nuestro Big O es técnicamente O (2n), pero dejemos las constantes para que nos quede O (n). Pero ahora tenemos que pensar en diferentes términos para las entradas. ¿Qué significa eso?

Si observamos el código anterior, podemos ver que ahora tenemos dos entradas. Uno podría tener un elemento de largo, el otro podría contener un millón de elementos. Entonces nuestra función ya no es O(n), es O(a + b). La n que usamos en nuestra notación es arbitraria, por lo que debemos reflejar ambas entradas en nuestra notación.

En este caso, nuestros bucles no están anidados. Si lo fueran, nuestro código sería O(n²), que sería un objetivo potencial para la refactorización. Por lo general, si hay bucles anidados, entonces está multiplicando en lugar de agregar las variables.

4. Elimina los términos no dominantes

Echa un vistazo a este código:

Así que tenemos un bucle único en la parte superior que es O(n) y luego un bucle anidado que es O(n²). Entonces nuestro total es O(n + n²). Pero como vimos en la regla #2, queremos eliminar las constantes. Entonces, ¿cuál de los dos términos es más importante para nosotros?

En este caso, descartamos O(n) y retenemos O(n²) ya que esto es más importante. Es el término dominante ya que tiene un impacto mucho mayor en el rendimiento.

Conclusión

¿Entonces cuál es el punto?

Si sabemos que solo trataremos con entradas pequeñas, Big O realmente no importa demasiado. Pero al escribir su código, debe considerar su escalabilidad.

Al prestar atención a Big O, tiene una visión del futuro y es más probable que escriba código que se pueda escalar de manera efectiva. Puede comenzar a ver el costo de su código y tomar decisiones informadas sobre cómo escribirlo.

Recursos

http://bichocheatsheet.com/

Notación Big-O _Lee y aprende gratis sobre el siguiente artículo: Notación Big-O_www.khanacademy.org