傅里叶变换：计算缩放作为向量长度的函数

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。这有意义吗（或者有 different/better 方法）？如果是这样，我将如何测量 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

timeit 库正是为此目的而创建的。

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

傅里叶变换：计算缩放作为向量长度的函数

Fourier Transform: Computational Scaling as a function of vector length

python

algorithm

python-2.7

big-o

dft