Как преодолеть превышение лимита времени (TLE)?

Многие программисты всегда утверждают, что проблемы в соревновательном программировании всегда заканчиваются TLE (превышение временного лимита). Основная проблема этой ошибки заключается в том, что она не позволит вам узнать, дойдет ли ваше решение до правильного решения или нет!

Почему приходит TLE?

• Ограничения онлайн-судьи: TLE возникает потому, что у онлайн-судьи есть некоторые ограничения, которые не позволяют обрабатывать инструкцию по истечении определенного времени, установленного установщиком задач (обычно 1 секунда).
• Конфигурация сервера: точное время, затрачиваемое на выполнение кода, зависит от скорости сервера, архитектуры сервера, ОС и, конечно же, от сложности алгоритма. Таким образом, разные серверы, такие как практика, codechef, SPOJ и т. Д., Могут иметь разную скорость выполнения. Оценив максимальное значение N (N - общее количество инструкций всего вашего кода), вы можете приблизительно оценить, произойдет ли TLE за 1 секунду.

   Максимальное значение N Временная сложность
     10 ^ 8 O (N) Пограничный регистр
     10 ^ 7 O (N) Может быть принято
     10 ^ 6 O (N) Идеально
     10 ^ 5 O (N * logN)
     10 ^ 3 O (N ^ 2)
     10 ^ 2 O (N ^ 3)
     10 ^ 9 O (logN) или Sqrt (N)
  

  Итак, проанализировав эту диаграмму, вы можете приблизительно оценить свою временную сложность и сделать свой код в пределах верхней границы.

• Метод чтения ввода и записи вывода слишком медленный: иногда методы, используемые программистом для ввода вывода, могут вызывать TLE.

Ошибки превышения лимита времени

• Измените методы ввода-вывода: вы должны выбрать правильные функции ввода-вывода и структуру данных, которые помогут вам в оптимизации.
  • В C ++ не используйте cin / cout - вместо этого используйте scanf и printf.
  • В Java не используйте сканер - используйте вместо него BufferedReader.
• Границы циклов могут быть уменьшены: внимательно прочитайте границы во входных данных, прежде чем писать свою программу, и попытайтесь выяснить, какие входные данные будут вызывать медленную работу вашей программы. Например, если проблема сообщает вам, что N <= 100000 или N <= 1000000, и ваша программа имеет вложенные циклы, каждый из которых достигает N, ваша программа никогда не будет достаточно быстрой.
• Оптимизируйте свой алгоритм: если после всего этого ничего не работает, вам следует попробовать изменить алгоритм или подход, который вы используете для решения вашей проблемы. Как правило, внутренние тестовые примеры разработаны таким образом, что вы сможете очистить их все, только если выберете наилучший из возможных алгоритмов.
• Ищите предложенные предложения: хотя это должен быть последний шаг, но вы должны просмотреть комментарии, приведенные ниже, любую проблему, в которой другие программисты могли бы дать подсказку о том, как проблему можно решить лучшим и более эффективным способом. И даже когда вы преодолеете TLE, попробуйте более исчерпывающие и угловые тестовые примеры для своей программы, чтобы проверить производительность.

В конце концов, с опытом вы обязательно узнаете, что делать, а чего не избегать TLE. Чем больше вы кодируете, тем больше узнаете о том, как бороться за TLE.

Практика сейчас

Эта статья предоставлена Шубхамом Бансалом. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью provide.geeksforgeeks.org или отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.