¿Cómo superar el límite de tiempo excedido (TLE)?

Muchos programadores siempre argumentan que los problemas en la Programación Competitiva siempre terminan con TLE (Exceso de Límite de Tiempo). ¡El principal problema con este error es que no le permitirá saber si su solución alcanzará la solución correcta o no! 
 

¿Por qué viene TLE?

• Restricciones del juez en línea: TLE surge porque el juez en línea tiene alguna restricción que no permitirá procesar la instrucción después de un cierto límite de tiempo dado por el creador del problema (1 segundo).
• Configuración del servidor: el tiempo exacto que tarda el código depende de la velocidad del servidor, la arquitectura del servidor, el sistema operativo y, por supuesto, de la complejidad del algoritmo. Por lo tanto, diferentes servidores como Practice, CodeChef, SPOJ, etc., pueden tener diferentes velocidades de ejecución. Al estimar el valor máximo de N (N es el número total de instrucciones de todo su código), puede estimar aproximadamente que el TLE ocurriría o no en 1 segundo. 
   

MAX value of N                       Time complexity
   10^9                              O(logN) or Sqrt(N)
   10^8                              O(N) Border case
   10^7                              O(N) Might be accepted
   10^6                              O(N) Perfect
   10^5                              O(N * logN)
   10^4                              O(N ^ 2)
   10^2                              O(N ^ 3)
   <= 160                            O(N ^ 4)
   <= 18                             O(2N*N2)
   <= 10                             O(N!), O(2N)

• Entonces, después de analizar este gráfico, puede estimar aproximadamente su complejidad de tiempo y hacer que su código esté dentro del límite superior.
• El método de lectura de entrada y escritura de salida es demasiado lento: a veces, los métodos utilizados por un programador para la entrada y salida pueden causar TLE.

Superar errores de límite de tiempo

• Cambie los métodos de entrada-salida: debe elegir las funciones de entrada-salida y la estructura de datos adecuadas que lo ayudarán en la optimización. 
  • En C++, no use cin/cout; use scanf e printf en su lugar.
  • En Java, no use un escáner, use un BufferedReader en su lugar.
• Los límites de los bucles pueden reducirse: lea los límites en la entrada cuidadosamente antes de escribir su programa, y ​​trate de averiguar qué entradas harán que su programa se ejecute más lento. Por ejemplo, si un problema le dice que N <= 100000 o N<=1000000, y su programa tiene bucles anidados, cada uno de los cuales sube a N, su programa nunca será lo suficientemente rápido.
• Optimice su algoritmo: si nada funciona después de todo esto, debe intentar cambiar el algoritmo o el enfoque que está utilizando para resolver su problema. En general, los casos de prueba internos están diseñados de tal manera que podrá borrarlos todos solo si elige el mejor algoritmo posible.
• Busque las sugerencias dadas: aunque este debería ser el último paso, debe mirar los comentarios que se dan a continuación, cualquier problema en el que otros programadores podrían haber dado una pista sobre cómo se puede resolver mejor y más eficientemente. E incluso cuando supere TLE, intente casos de prueba más exhaustivos y de esquina contra su programa para verificar el rendimiento.

En última instancia, con la experiencia, seguramente llegará a saber qué hacer y qué no para evitar los TLE. Cuanto más codifiques, más sabrás sobre cómo competir por TLE. 

practica ahora 

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Escriba comentarios si encuentra algo incorrecto o si tiene más información sobre el tema tratado anteriormente.