写一个傅里叶算法

对于一个长度为 N 的序列 a，傅里叶变换的定义为：

$$ \begin{aligned} A_k &= \sum_{n=0}^{N-1} a_n e^{-\frac{2\pi ikn}{N}} \ &= \sum_{n=0}^{N-1} a_n [\cos(\frac{2\pi kn}{N}) - i\sin(\frac{2\pi kn}{N})] \end{aligned} $$

其中，$k=0, 1, 2, ..., N-1$.

傅里叶变换的逆变换定义为：

$$ a_n = \frac{1}{N} \sum_{k=0}^{N-1} A_k e^{\frac{2\pi ikn}{N}} $$

其中，$n=0, 1, 2, ..., N-1$.

这里实现一个快速傅里叶变换（FFT）算法，时间复杂度为 $O(N\log N)$。

import cmath

def fft(a):
    N = len(a)
    if N == 1:
        return a
    w_n = cmath.exp(-2j * cmath.pi / N)
    w = 1
    a0 = fft(a[::2])
    a1 = fft(a[1::2])
    ans = [0] * N
    for i in range(N // 2):
        ans[i] = a0[i] + w * a1[i]
        ans[i + N // 2] = a0[i] - w * a1[i]
        w *= w_n
    return ans

其中，参数 a 是一个长度为 N 的复数序列。返回值是一个长度为 N 的复数序列，代表输入序列的傅里叶变换结果。