高速 Fourier 変換

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /fast-fourier-transform#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /fast-fourier-transform#noredirect を利用してください。
name
高速 Fourier 変換
short description
高速 Fourier 変換とは、離散 Fourier 変換を $O(n \log n)$ で行うアルゴリズムである。高速な多項式乗算の実装などに用いられる。
time complexity
$O(n \log n)$