The Negligible Lab

はじめに FFTと私 高速フーリエ変換(Fast Fourier Transform, FFT)は，通常の離散フーリエ変換(Discrete Fourier Transform, DFT)に比べて非常に高速なアルゴリズムとして知られており，ランダウの記号を用いると，DFTの計算量がO(N2)であるところ，FFTではO(N log N)になるようです。このため，理学・工学の幅広い分野で…