Избегайте TLE в Python в соревновательном программировании

Опубликовано: 30 Ноября, 2021

Причины получения TLE :

Он медленнее по сравнению с другими языками программирования.
Он предлагает более медленный ввод / вывод.
Он имеет меньшую глубину рекурсии, что часто дает TLE в задачах рекурсии и графов.

Советы, как избежать TLE с Python :

Переход к итерационному подходу :

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

Программа 1:

Ниже приведен код, показывающий время, необходимое для вычисления факториала числа в обоих подходах:

Python3

 # Program to show the time taken in
 # iteration and recursion
 
time import
 
# Recursive function to find factorial
 # of the given number N
 def factorial(N):
   
      # Base Case
    if N = = 0 :
        return 1
       
    # Recursive Call
    return N * factorial(N - 1 )
 
# Driver Code
 if __name__ = = '__main__' :
    n = 20
 
    # Find the time taken for the
    # recursive approach
    start = time.perf_counter()
    print ( "Calculated using recursion: " , factorial(n))
     
    end = time.perf_counter()
    print ( "Time taken in recursion: " , "{0:.9f}" . format (end - start))
 
    # Find time taken for iterative
    # approach
    start = time.perf_counter()
    result = 1
     
    while n > 0 :
        result * = n
        n - = 1
         
    print ( "Calculated using the iterative method: " , result)
     
    end = time.perf_counter()
    print ( "Time taken in iteration: " , "{0:.9f}" . format (end - start)) 

Выход:

Вычислено с использованием рекурсии: 2432902008176640000
Время, затраченное на рекурсию: 0,000015925
Рассчитано итерационным методом: 2432902008176640000
Время, затраченное на итерацию: 0,000009279

Python Technical Scripter Олимпиады по программированию

Избегайте TLE в Python в соревновательном программировании

Переход к итерационному подходу :

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ