高速フーリエ変換こうそくふーりえへんかん

高速こうそくフーリエ変換へんかん（FFT）とは、信号しんごうを周波数しゅうはすう成分せいぶんに分解ぶんかいする離散りさんフーリエ変換へんかんを、$O(n\log n)$ という少すくない計算けいさん量りょうで行おこなうアルゴリズムです。1 の $n$乗根じょうこんの対称たいしょう性せいを利用りようするのが鍵かぎです。（発展はってん）

方法ほうほう	計算けいさん量りょう
素朴そぼくな離散りさんフーリエ変換へんかん	$O\left(n^2\right)$
高速こうそくフーリエ変換へんかん（FFT）	$O(n\log n)$

FFT は、1 の $n$乗根じょうこん${\omega }_k=\cos \frac{2\pi k}{n}+i\sin \frac{2\pi k}{n}$ がもつ規則きそく的てきな対称たいしょう性せいを使つかって、計算けいさんを半分はんぶんずつに分わけて繰くり返かえす「分割ぶんかつ統治とうち」の代表だいひょう例れいです。たとえば $n=1024$ のデータでも、素朴そぼくな方法ほうほうより圧倒的あっとうてきに速はやく処理しょりできます。音声おんせい処理しょり・画像がぞう圧縮あっしゅく（JPEG）・通信つうしん（Wi-Fi、LTE）など、デジタル信号しんごうを扱あつかう場面ばめんで必須ひっすの技術ぎじゅつです。

ポイント 「1 の $n$乗根じょうこんの対称たいしょう性せい」が高速こうそく化かの核心かくしん。複素数ふくそすう平面へいめんで学まなぶ $n$乗根じょうこんが、現代げんだいのデジタル技術ぎじゅつを支ささえている好例こうれい。