傅立葉變換：作爲矢量長度的函數的計算縮放

Question

如果我要使用下面定義的函數來計算離散傅里葉變換，我將如何顯示計算作爲矢量的函數而縮放爲O（N^2）長度。

def dft(y): 
    N = len(y) 
    c = np.zeros(N//2+1,complex) 
    for k in range(N//2+1): 
     for n in range(N): 
      c[k] += y[k]*np.exp(-2j*np.pi*k*n/N) 
    return c 

從我的理解，如果一個算法規模爲O（N^2）意味着它是二次和環路的運行時間正比於N的平方如果N加倍...那麼運行時間會增加N * N。

我的第一個想法是運行一個程序，當我轉換一個長度等於N的值的數組，然後加倍這些值（加倍N），並且顯示這兩者之間的運行時間差是N^2 。這是否有意義（或者有不同的/更好的方式）？如果是的話，我將如何測量python中的運行時間？

謝謝。

Answer 1

運行時間？你可以在開始時創建一個計數器，每次完成時將其加1。因此，在第二個for循環中，只需將計數器加1，並在程序完成時打印計數器。這將顯示所需的計算量。

count = 0 
def dft(y): 
    N = len(y) 
    c = np.zeros(N//2+1,complex) 
    for k in range(N//2+1): 
     for n in range(N): 
      c[k] += y[k]*np.exp(-2j*np.pi*k*n/N) 
      count+=1 
    return c 

print(count) 

Answer 2

一點取決於你想測量你可以使用time.clock（我認爲這是最接近你想要的這裏 - 它測量你的程序實際上得到運行的時間股）什麼時間或datetime.datetime.now。

你只需要計算完成前後的時間。喜歡的東西：

t0 = time.clock() 
dft() 
t1 = time.clock() 

print("Time ellapsed: {0}".format(t1-t0)) 

請注意，您正在尋找加倍N時是什麼的時候翻了兩番。

Answer 3

線計算的係數重複

倍。然後，你需要證明存在常數M和N個那個

值如N趨近於無窮大。那麼你已經顯示

。

Answer 4

時間庫是完全用於此目的。

https://docs.python.org/2/library/timeit.html

from timeit import timeit 

for i in [10, 100, 1000, ...]: 
    y = generate_array(i) 
    timeit('dft(y)')