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