写一段实现快速傅里叶变换的代码

好的，以下是一个基于Cooley-Tukey算法的快速傅里叶变换代码实现：

import numpy as np

def fft(x):
    n = x.shape[0]
    if n == 1:
        return x
    even = fft(x[::2])
    odd = fft(x[1::2])
    T = [np.exp(-2j * np.pi * k/n) * odd[k] for k in range(n//2)]
    return np.concatenate([even + T, even - T])

此代码实现了递归的快速傅里叶变换过程，它将输入数组x分为偶数项和奇数项，对偶数项和奇数项分别进行快速傅里叶变换，然后将它们组合起来得到最终的结果。算法的复杂度是O(nlogn)。