快速傅里叶变换的python代码实现

以下是Python中进行快速傅里叶变换的代码实现：

import numpy as np

def fft(x):
    n = len(x)
    if n == 1:
        return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    factor = np.exp(-2j * np.pi * np.arange(n) / n)
    return np.concatenate([even + factor[:n//2] * odd,
                           even + factor[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()`函数接受一个长度为 $2^k$ 的序列，并返回其傅里叶变换结果。上面的代码实现了递归式的 Cooley-Tukey FFT 算法。