这些Python函数没有预期的运行时间

(我不确定这个问题是属于这里还是CS论坛.我把它保留在这里因为它有特定于Python的代码.如果需要请迁移!)我现在正在研究算法,使用Python作为我的首选工具.今天,我想绘制一个简单问题的三种变体的运行时间:计算给定序列(列表)的前缀平均值.

以下是三种变体:

import timeit

seq = [20, 45, 45, 40, 12, 48, 67, 90, 0, 56, 12, 45, 67, 45, 34, 32, 20]

# Quadratic running time
def quad (S):
    n = len(S)
    A = [0] * n

    for j in range(n):
        total = 0
        for i in range(j+1):
            total += S[i]
        A[j] = total / (j+1)

    return A

# Use prev result
def prev (S):
    n = len(S)
    A = [0] * n

    for j in range(n):
        if j == 0:
            A[j] = S[j]
        else:
            A[j] = (A[j-1]*j + S[j]) / (j+1)
    return A

# Use Python's sum method
def summ (S):
    n = len(S)
    A = [0] * n

    for j in range(n):
        A[j] = sum(S[0:j+1])/(j+1)
    return A

def plot_func (name):
    for i in range(0, 1000000, 100000):
        t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name))
        print(i, ',', t.timeit(number=i))

plot_func('quad')
plot_func('prev')
plot_func('summ')

所以我正在收集三种算法的运行时间并绘制它们.我的最终数据看起来像这样:

Input size  Quadratic   Prev    Summ
(x100000)
1   4.92E-007   7.78E-007   3.47E-007
2   1.582717351 0.603501161 0.750457885
3   3.205707528 1.176623609 1.508853766
4   4.796092943 1.76059924  2.295842737
5   6.457349465 2.34945291  3.112500982
6   8.057410897 2.947556047 3.882303307
7   9.59740446  3.520847787 4.654968896
8   11.36328988 4.122617632 5.412608518
9   12.776150393    4.703240974 6.181500295
10  14.704703677    5.282404892 6.882074295

绘制时,这些数字会导致:

现在,根据教科书,我下面的功能quad和summ应该在二次时间运行,而prev会以线性时间运行.我可以看到它prev明显快于quad并且速度稍快summ,但所有这些对我来说都像线性函数!而且,summ和之间的差距很小prev.

有人可以解释一下是什么问题吗？

算法的渐近复杂性意味着它与输入长度的相关性.在这里,您不会在运行之间更改输入大小,只需更改运行每个算法的次数(作为参数timeit()):

   for i in range(0, 1000000, 100000):
        t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name))
        print(i, ',', t.timeit(number=i))

要进行适当的比较,请在运行之间更改序列的长度.