为什么迭代算法查找列表总和所花费的时间不会随大小而均匀增加？

Question

我想了解在对数组求和的迭代方法和递归方法之间，时间复杂度的差异有多大。因此，我绘制了“时间”与“列表大小”图，以获得相当不错的size（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()

Answer 1

（（1）您正在混合两个图。

迭代式保持固定，而递归式增大。

一种可能的解释是，与迭代调用相比，递归调用生成堆栈条目并需要更多的计算时间。

（（2）您需要增加数组的大小，因为较小的大小可能会由于参考位置而引起尖峰。

（（3）您需要在多个时期重复进行实验，以确保由于其他一些过程造成的随机峰值干扰资源的平均分配。

Answer 2

与列表调整大小策略有关。 https://www.scrygroup.com/tutorial/2018-06-18/cpython-lists-cache-locality/

此超额分配与列表大小成正比，为腾出空间以获得额外的增长。过度分配是轻微的，但是足以长期提供线性时间摊销行为在表现不佳的情况下的appends（）序列系统realloc（）。增长模式是：0、4、8、16、25、35、46、58、72、88，...注意：new_allocated不会溢出，因为可能的最大值是PY_SSIZE_T_MAX *（9/8）+ 6，始终适合size_t。

而不是每次修改后都重新分配，它仅在具有预定义模式的某些点上调整大小。