编写一个FFT函数，实现FFT功能，并和系统函数fft比较一下效率

FFT（快速傅里叶变换）是一种高效的计算DFT（离散傅里叶变换）的算法，它可以将一个n点序列的DFT计算复杂度从O(n^2)降低至O(nlogn)。

下面是一个简单的FFT实现的伪代码：

function FFT(x)
    if x.length = 1 then
        return x

    evenIndex = 0
    oddIndex = 0
    even = []
    odd = []
    for i = 0 to x.length - 1 do
        if i is even then
            even[evenIndex] = x[i]
            evenIndex = evenIndex + 1
        else
            odd[oddIndex] = x[i]
            oddIndex = oddIndex + 1

    even = FFT(even)
    odd = FFT(odd)

    result = []
    for k = 0 to x.length - 1 do
        t = odd[k % odd.length] * exp(-2iπk/n)
        result[k] = even[k % even.length] + t

    return result
end function

其中exp(-2iπk/n)是旋转因子，可以预先计算并存储以提高效率。

关于与系统函数fft的比较，这里提供一种可能的方法。首先，我们需要在相同的数据集上运行自己实现的FFT和系统函数fft，并记录它们的运行时间。然后，我们可以比较它们的运行时间来判断它们的效率。同时，我们还需要比较它们的结果是否一致，以确保自己实现的FFT的正确性。