●高速フーリエ変換
Fast Fourier Transform。通称FFT。
大量のサンプリングデータをコンピューター上で素早く離散フーリエ変換するために考えられたアルゴリズム。
周期Ｎの離散フーリエ変換を普通に計算すると、計算量はO(N2)だが、高速フーリエ変換を用いることでなんとその計算量をO(Nlog2N)まで落とすことができる。N=65536とすると、通常は4,294,967,296回、約43億回の計算をしなければならないところが、たったの1,048,576回、約100万回程度の計算で済むことになる。計算量は1/4096だ。
具体的なアルゴリズムについては専門のサイトを参照のこと。
とりあえず語の定義だけ聞かれたら、フーリエ変換を高速にやることだよ、と文字通り答えれば正解。