Costo, escala y Big O
Predice cómo crece el trabajo y luego mide la parte que importa.
AL TERMINAR, PODRÁS
- Distinguir el crecimiento asintótico del tiempo transcurrido
- Reconocer trabajo lineal, logarítmico y cuadrático
- Diseñar una comparación de rendimiento justa
Descripción del diagrama: O(1); O(log n); O(n); O(n²)
Cuenta trabajo antes que segundos
La notación Big O describe un límite superior de cómo crece el uso de un recurso según el tamaño de la entrada, bajo supuestos declarados.
Revisar cada trabajo una vez es trabajo lineal, y se escribe O(n). Comparar cada par hace aproximadamente n al cuadrado comparaciones, o O(n²). Dividir a la mitad una región de búsqueda una y otra vez toma O(log n) pasos.
Estas descripciones omiten factores constantes y detalles de la máquina. Sirven para predecir el crecimiento, no para afirmar que una implementación siempre es más rápida con una entrada diminuta. Define qué representa n antes de usar la notación.
El trabajo oculto también cuenta
Una línea corta puede esconder un bucle.
Comprobar si un elemento está en una lista recorre sus elementos; hacerlo dentro de otro bucle puede producir trabajo cuadrático. Un set puede hacer que esa comprobación tome tiempo constante en promedio, a cambio de memoria extra y del cálculo de hashes. Copiar una lista o hacer slicing (tomar un trozo) de casi toda ella también cuesta tiempo y espacio proporcionales a los elementos copiados.
En Relay, reconstruir toda la cola para procesar un solo elemento puede dominar el manejo real del trabajo aunque el código se vea elegante.
Mide una hipótesis realista
Un benchmark (prueba de rendimiento) debería responder una pregunta como «¿quitar el frente de esta cola domina el procesamiento con cien mil trabajos?».
Mantén comparables la entrada, la preparación y el entorno. Separa la preparación de la operación que mides, repite las mediciones y examina más de un tamaño de entrada. El tiempo de reloj puede incluir esperas; un profiler (perfilador) ayuda a ubicar dónde se gasta el tiempo de ejecución.
Optimiza después de identificar una restricción y conserva una versión base legible. Acelerar diez veces un componente que usa el uno por ciento del tiempo total tiene un impacto limitado.
ERROR FRECUENTE
Tratar O(1) como instantáneo u O(n) como lento. El tamaño de la entrada, los factores constantes, la memoria y el cuello de botella real siguen importando.
INTÉNTALO TÚ
Estima las comparaciones de dos bucles anidados sobre 100, 1.000 y 10.000 trabajos. Luego explica por qué multiplicar la entrada por diez puede multiplicar por cien el trabajo cuadrático.
Decide en el laboratorio.
El checkpoint de dos preguntas, tus notas y tu progreso guardado están en el laboratorio. Gratis y sin cuenta.
Abrir en el laboratorio ↗CONÉCTALO CON RELAY
Compara quitar el frente de una lista con quitarlo de un deque para varios tamaños de cola. Registra los tamaños de entrada y las limitaciones de tus mediciones.