Я хотел посмотреть, как drasti c - это разница во временной сложности между итеративным и рекурсивным подходами для суммирования массива. Поэтому я построил график зависимости времени от размера списка для довольно приличного диапазона значений размера (995). То, что я получил, было в значительной степени тем, что я хотел, кроме чего-то неожиданного, привлекшего мое внимание. График можно увидеть здесь 1
Как и ожидалось, рекурсивный граф (синий) остается близким к нулю для всех значений размера, в то время как итерационный граф (зеленый) растет. Что меня смущает, так это те неровности, которые зеленая линия внезапно принимает только для определенных значений, а затем возвращается обратно. Почему это происходит?
Вот код, который я написал:
import matplotlib.pyplot as plt
from time import time
def sum_rec(lst): # Sums recursively
if len(lst) == 0:
return 0
return lst[0]+sum_rec(lst[1:])
def sum_iter(lst): # Sums iteratively
Sum = 0
for i in range(len(lst)):
Sum += i
return Sum
def check_time(lst): # Returns the time taken for both algorithms
start = time()
Sum = sum_iter(lst)
end = time()
t_iter = end - start
start = time()
Sum = sum_rec(lst)
end = time()
t_rec = end - start
return t_iter, t_rec
N = [n for n in range(995)]
T1 = [] # for iterative function
T2 = [] # for recursive function
for n in N: # values on the x-axis
lst = [i for i in range(n)]
t_iter, t_rec = check_time(lst)
T1.append(t_iter)
T2.append(t_rec)
plt.plot(N,T1)
plt.plot(N,T2) # Both plotted on graph
plt.show()