Python 实现离散傅里叶变换 (DFT) 并比较 DFT 和 FFT 速度

以下是使用 for 循环实现离散傅里叶变换 (DFT) 的示例代码：

import numpy as np
import time

def dft(x):
    N = len(x)
    X = np.zeros(N, dtype=np.complex128)
    for k in range(N):
        for n in range(N):
            X[k] += x[n] * np.exp(-2j * np.pi * k * n / N)
    return X

# 输入信号
x = np.random.random(1024)

# 计算DFT并记录时间
start_time = time.time()
X = dft(x)
end_time = time.time()
dft_time = end_time - start_time

# 使用已有的快速傅里叶变换函数并记录时间
start_time = time.time()
X_fast = np.fft.fft(x)
end_time = time.time()
fft_time = end_time - start_time

print('DFT运算时间：', dft_time)
print('FFT运算时间：', fft_time)

在上面的代码中，我们首先定义了一个 dft 函数来实现离散傅里叶变换。然后，我们生成了一个 1024 个随机数的信号作为输入信号。接下来，我们分别使用 dft 函数和 NumPy 的 fft 函数计算 DFT，并记录下运行时间。最后，我们打印出两种方法的运算时间。

请注意，由于 DFT 的计算复杂度为 O(N^2)，而快速傅里叶变换 (FFT) 的计算复杂度为 O(NlogN)，因此使用 FFT 计算 DFT 的速度通常更快。根据上述代码中生成的随机信号的长度不同，你可以看到 FFT 的运算时间明显优于 DFT 的运算时间。