高速フーリエ変換 (Fast Fourier Transform, FFT)

離散フーリエ変換の式

X(k)=∑n=0N−1x(n)e−i2πNkn X (k) = \sum_{n = 0}^{N - 1} x (n) e^{-i \frac{2\pi}{N} kn}

参考資料