用python语言编写一段进行傅里叶变换的函数

这是一段使用 Python 语言编写的进行傅里叶变换的函数：

import numpy as np

def fft(x):
    """进行傅里叶变换"""
    x = np.asarray(x, dtype=float)
    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 [even[k] + T[k] for k in range(N//2)] + [even[k] - T[k] for k in range(N//2)]

这段函数使用了递归的方法，将输入的信号 `x` 分成两部分，分别对这两部分进行傅里叶变换，然后将结果按照傅里叶变换的公式合并起来。

需要注意的是，这段函数的时间复杂度为 $O(N\log N)$，因此对于大规模的信号可能会比较慢。对于实际应用中的信号，建议使用更快的傅里叶变换算法，例如 Cooley-Tukey 算法。