Notación Big O: ¿Qué es y por qué es importante?

¡Este es divertido! Comunicarse con Big O es una de las primeras transiciones deslumbrantes para los desarrolladores al principio de su carrera.

Veamos por qué.

Pero primero, una parada en boxes. ¿Recuerdas esos problemas de palabras absolutamente ridículos de la escuela primaria?

Sally fue al supermercado y compró 37 sandías. Ella tenía $20 dólares. Cada sandía cuesta $0.70. ¿Cuánto dinero tiene Sally cuando llega a casa?

¿Te quedaste pensando, "¿Cómo demonios va a llegar Sally a casa? ¡¿Con 37 sandías?! $6.00 no serán suficientes para comprar un Uber con suficiente espacio para las sandías... ¿qué está haciendo Sally?".

Sally tonta.

Algunas personas dicen que esto es perder el bosque por los árboles. Yo digo que es solo una forma terriblemente perezosa de construir problemas de práctica.

El propósito de Big O Notation es poder hablar, literalmente comunicarse con otras personas , sobre una cualidad de nuestro oficio. El enfoque particular aquí es permitir la comparación entre soluciones en el peor de los casos a medida que aumenta el tamaño de la entrada.

Queremos poder hablar sobre posibles soluciones ( lo mismo que decir: algoritmos ) en abstracto. Este es un punto crucial: en abstracto . No nos importa , en absoluto , la información que tenemos . Cuando jugamos con estas ideas, asumimos un conjunto de datos teóricamente gigantesco, pero finito.

Cuando pensamos en los datos que tenemos , estamos razonando en concreto. Cuando pensamos en la notación Big O, estamos razonando en abstracto. Es FÁCIL volver al razonamiento concreto. Aquí es donde pasamos la mayor parte de la vida. Es fácil, generalmente obvio y cómodo.

¿Debo cruzar la calle ahora? ¿Hay un coche? ¿No? Está bien, cruz.

¡No lo hagas cuando razones en abstracto!

Definiciones, Rápidamente

¿Te importa si te hago un favor aquí? Hay un montón de términos matemáticos que también pueden interferir. Aquí hay una imagen, en orden, del mejor al peor de los casos, para algunos términos comunes de Big O. Los necesitamos para poder pensar y aprender en lugar de atascarnos en la terminología.

O (1) - "Tiempo constante"

No importa cuán grande sea la entrada, el sistema siempre devuelve el resultado en la misma cantidad de tiempo.

O (registro n) - "Tiempo de registro"

A medida que la solución (o algoritmo) itera sobre la entrada, ¡cada iteración se vuelve más rápida!

O (n) - "Tiempo lineal"

A medida que el algoritmo itera, cada iteración toma la misma cantidad de tiempo que la iteración anterior.

O (n log n) - no hay terminología sofisticada aquí

Muestra que las ideas se pueden combinar (yikes). A medida que iteramos, cada iteración se vuelve más lenta, pero se vuelve más lenta con bastante lentitud.

O(n^2) - "n al cuadrado"

Para cada iteración, las iteraciones se vuelven más lentas con bastante rapidez.

O(n!) - "n factorial"

Para cada iteración, las iteraciones se vuelven más lentas súper rápido.

El objetivo es tratar de mantenerse lo más lejos posible de "n factorial" y tratar de no ser mucho peor que Constant.

Con todo eso entendido, ahora tratemos de cerrar la brecha.

Cerrar la brecha entre el pensamiento concreto y el abstracto

Comprender la notación Big O

La notación Big O se utiliza para describir el rendimiento o la complejidad de un algoritmo (solución). Proporciona una comprensión de alto nivel de cómo funcionará un algoritmo (solución) a medida que crece el tamaño de la entrada.

Por ejemplo, un algoritmo con complejidad O(n) tendrá su tiempo de ejecución incrementado linealmente con el tamaño de la entrada.

Pensamiento concreto vs abstracto

El desafío surge cuando los desarrolladores confunden el razonamiento sobre datos específicos con el razonamiento sobre el algoritmo en sí. Frases como "pero estos datos son reales" pueden indicar esta confusión.

Si bien razonar sobre los datos reales puede ayudarlo a comenzar, es vital separar la solución de la entrada actual.

¿Por qué el malentendido?

Los desarrolladores de carrera temprana pueden cometer este error debido a la falta de experiencia con problemas de mayor escala o estar demasiado absortos en los detalles de un problema actual. Es esencial separar los detalles concretos de la complejidad abstracta para crear soluciones escalables.

Consecuencias prácticas

Cuando la entrada aumenta 100 o 100 000 veces, ¿qué sucede con el algoritmo? La complejidad de una solución increíblemente compleja podría desmoronarse con un conjunto de datos más grande.

Un algoritmo que parece correcto para conjuntos de datos pequeños puede fallar drásticamente con los más grandes, lo que genera problemas de rendimiento y otros desafíos.

Aprendiendo a pensar en abstracto

Desarrollar la capacidad de pensar de manera abstracta sobre los problemas requiere práctica y orientación. Algunas estrategias incluyen:

• Creación de modelos abstractos : Representación de problemas de forma generalizada.

• Analizar algoritmos por separado de los datos : evaluar cómo se comporta el algoritmo independientemente de los puntos de datos específicos.

• Creación de escenarios de escala : Imaginar cómo funcionará el algoritmo con diferentes tamaños de entrada.

El pensamiento abstracto en general, y la notación Big O específicamente, son habilidades esenciales en el diseño de algoritmos; en otras palabras, encontrar una solución a un problema.

Al aprender a separar la complejidad del problema de la complejidad del algoritmo , los desarrolladores pueden evitar las trampas comunes y mejorar sus habilidades de resolución de problemas cuando trabajan solos Y mejorar drásticamente la capacidad de trabajar junto con otras personas que han invertido el tiempo de manera similar para aprender a comunicarse de esta manera.

Los problemas complejos a menudo no requieren soluciones complejas. (Sally probablemente no necesitaba 37 sandías para empezar... ¡¿qué va a hacer con 37 sandías?!)