とりあえず定義を書いておく．複素数列xに対する離散フーリエ変換は次の式で定義される．逆変換はこっち．で，見て分かる通りn*n回の乗算が必要なので，これをn lg n回に落とすのが高速フーリエ変換．

正直・・・．うん．