これらのPythonの関数は、私はよ（私はこの質問はここに属しているかCSのフォーラムかはわからない。それは、Python固有のコードを持っているので、私は必要に応じて移行してください。ここでそれを保持！）

Question

を期待通りに時間を実行している必要はありません。 Pythonを私の選択の道具として使用して、最近のアルゴリズムを研究しています。今日、私は実行時間を簡単な問題の3つのバリエーションにプロットしたいと考えました：与えられたシーケンス（リスト）のプレフィックス平均を計算します。

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') 

は、だから私は3つのアルゴリズムの実行中の時間を収集し、それらをプロットしています：ここで

は3つのバリエーションがあります。プロットすると

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)) 

適切な比較を取得するには、間にあなたのシーケンスの長さを変更します走る