GPT 请给出一个用python实现的快速傅里叶算法的示例代码

下面是一个使用 NumPy 实现快速傅里叶变换（FFT）的示例代码：

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 * np.arange(N) / N)
    return np.concatenate([even + T[:N // 2] * odd,
                           even + T[N // 2:] * odd])

使用方法：

import numpy as np
x = np.random.random(1024)
y = np.fft.fft(x)

这里我们使用了 NumPy 中自带的 FFT 函数作为参考。