python fft 代码

下面是一个简单的 Python FFT 代码示例：

import numpy as np

def fft(x):
    # 如果 x 的长度为1，返回 x
    if len(x) == 1:
        return x
    else:
        # 将 x 分成两部分
        even = fft(x[0::2])
        odd = fft(x[1::2])
        
        # 计算 DFT
        n = len(x)
        factor = np.exp(-2j * np.pi * np.arange(n) / n)
        return np.concatenate([even + factor[:int(n/2)] * odd,
                               even + factor[int(n/2):] * odd])

# 示例
x = np.array([1, 2, 3, 4])
print(fft(x))

输出结果为：

[10. -0.j -2.+2.j -2. -0.j -2.-2.j]

其中，`fft` 函数是递归地计算 DFT 的，使用了分治法的思想。具体来说，如果输入序列的长度为 $n$，则将其分成两部分，长度都为 $n/2$，然后对这两部分分别计算 DFT，并将结果合并起来。如果输入序列的长度为 $1$，则直接返回该序列。在计算 DFT 的过程中，使用了蝴蝶运算，以实现 $O(n \log n)$ 的时间复杂度。