円周率.jp > 多数桁計算 > FFT > 計算量の導出

計算量の導出

ここでは FFT の計算量が O(n logn) になることについての簡単な説明を行う.

ちなみに, 多倍長乗算はフーリエ変換と乗算との関係に記載したように,

  1. 2 回の FFT … O(n logn)
  2. 要素ごとの積 … O(n)
  3. 逆 FFT … O(n logn)

という手順で行うことができるので,その計算量は O(n logn) になる.

この計算量を示す過程には 2 種類の導き方があるので, その両者について説明する. その際,変換元のデータは時間軸上のデータ, 変換後のデータは周波数軸上のデータ, というように捉えると名前が分かりやすい.

時間間引きFFT

定義式のうち,j が奇数のものと偶数のものに分ける.

Ak\sum_{j=0}%5e{n/2-1} a2jω2jkωk\sum_{j=0}%5e{n/2-1} a2j+1ω2jk     …(1)

こうなると右辺の Σ の中は項数 n/2 の DFT になっているので,Ak の方もそれに合わせる. ただしこちら側も k の偶奇で分割しては意味がないので kkn/2 に分けて k ∈ [0,n/2) にする.

Ak+n/2\sum_{j=0}%5e{n/2-1} a2jω2jkωk\sum_{j=0}%5e{n/2-1} a2j+1ω2jk     …(2)

ここで (1) 式と (2) 式を同時に求めることを考えると, \sum_{j=0}%5e{n/2-1} a2jω2jkωk\sum_{j=0}%5e{n/2-1} a2j+1ω2jk を求めればよいことが分かる. また,それらは項数 n/2 の DFT であるため, この方法を再帰的に適用することができることも分かる.

ここで項数 n の FFT の計算量を T(n) とすると,先ほどの再帰的な FFT 分割適用は

T(n) = 2T(n/2) + Cn

となる.末尾の Cnωjk の乗算や2つのFFTの結果の加減算にかかるコストを示している.この式を解くと

T(n)=O(n logn)

となる.

周波数間引きFFT

今度は逆に,定義式のうち j (0≦jn) を jjn/2 (0≦jn/2) とに分け, k を偶奇に分ける.

A2k \sum_{j=0}%5e{n/2-1} ajω2jk \sum_{j=0}%5e{n/2-1} aj+n/2ω2jk \sum_{j=0}%5e{n/2-1} \Bigl(ajaj+n/2\Bigr) ω2jk     …(3)
A2k+1 \sum_{j=0}%5e{n/2-1}ajωjω2jk \sum_{j=0}%5e{n/2-1}aj+n/2ωjω2jk \sum_{j=0}%5e{n/2-1} \Bigl( ajaj+n/2\Bigr) ωj ω2jk     …(4)

ここで (3) 式と (4) 式については

aj(0)ajaj+n/2,   aj(1) = (ajaj+n/2ωj

の演算は同時にできる. この変換を再帰的に適用させると,n=4 程度で実質的に ω2jk の乗算に当たる演算が無くなる.