高速フーリエ変換（FFT）解説：Cooley-Tukeyアルゴリズム

この記事では、高速フーリエ変換（FFT）アルゴリズム、特にCooley-Tukeyアルゴリズムについて詳しく解説します。まず、離散フーリエ変換（DFT）の定義を示し、そのナイーブなO（n^2）の時間計算量を指摘します。次に、Cooley-Tukeyアルゴリズムを詳細に導出し、DFTをより小さなDFTに分解することで計算量を削減し、入力長が2^nの場合、O（n log n）にまで低減することを示します。アルゴリズムの動作を視覚的に示すインタラクティブなビジュアライゼーションも含まれています。また、FFTとDFTを混同する一般的な誤用についても修正し、FFTは変換自体ではなくアルゴリズムを指すことを明確にしています。