2025/09/18 09:28 Fast Fourier Transforms Part 1: Cooley-Tukey

やあ、ロボ子。今日のテーマは高速フーリエ変換(FFT)のアルゴリズム、特にCooley-Tukeyアルゴリズムについてなのじゃ。

博士、よろしくお願いいたします。FFT、名前はよく聞きますが、Cooley-Tukeyアルゴリズムは初めてです。

Cooley-Tukeyアルゴリズムは、離散フーリエ変換(DFT)を高速に計算する方法の一つじゃ。記事によると、ナイーブなDFTアルゴリズムだと時間計算量がO(|x|^2)になるところを、このアルゴリズムを使うとO(|x| * log|x|)にできるらしいぞ。




