La regla práctica de 10^8

Un juez en línea típico ejecuta aproximadamente 10^8 operaciones sencillas por segundo. Ese número es su presupuesto total para ejecutar el programa. 💡

Multiplique el número de operaciones por el trabajo de cada paso y compárelo con el límite de tiempo. Si los pasos caben en el presupuesto, probablemente pasará.

Un recorrido O(n) con n = 10^6 requiere solo un millón de pasos, muy por debajo del presupuesto. Las soluciones lineales casi siempre pasan con holgura.

Para n = 10^6, una ordenación O(n log n) requiere unos 2 × 10^7 pasos. Sigue estando dentro del presupuesto de un segundo, por lo que ordenar rara vez es el cuello de botella.

Un enfoque O(n^2) alcanza el presupuesto cerca de n = 10^4, cuando cuesta 10^8 pasos. A partir de ahí, lo cuadrático empieza a exceder el límite de tiempo.

Una solución O(n^3) solo funciona hasta aproximadamente n = 500. Al elevar ese valor al cubo se obtienen unos 10^8 pasos, justo en el límite del presupuesto.

O(2^n) se duplica en cada paso, así que solo funciona con valores pequeños de n, alrededor de 20 a 25. Después, el número de operaciones se dispara por encima de 10^8.

Python es más lento en cada paso, así que considere que el presupuesto se acerca más a 10^7 en bucles ajustados. Sea conservador cuando las restricciones estén cerca del límite.

La regla de 10^8 cuenta pasos sencillos. Un trabajo costoso dentro de un bucle, como construir cadenas, añade un factor constante que reduce su presupuesto real.

El límite de tiempo suele ser de 1 o 2 segundos. Un límite de 2 segundos aproximadamente duplica su presupuesto y le da un poco más de margen.

Sustituya siempre n en su complejidad y compárela primero con 10^8. Esta rápida comprobación de plausibilidad evita que programe una solución destinada a fallar.

Ponga en práctica la regla de 10^8.

Ahora puede relacionar las operaciones con el tiempo: aproximadamente 10^8 por segundo. O(n) y n log n son seguros, O(n^2) tiene un límite cercano a 10^4 y debe comprobarlo antes de programar. ✅