Эти функции Python не имеют ожидаемого времени работы

Question

(Я не уверен, что этот вопрос принадлежит или форум 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.

Не могли бы вы объяснить, что случилось?

Answer 1

Асимптотическая сложность алгоритма означает его зависимость от входной длины. Здесь вы не изменить размер входного между запусками, вы просто изменить количество времени для запуска каждого алгоритма (в качестве параметра 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)) 

Чтобы получить правильное сравнение, изменение длины вашей последовательности между пробеги.