高速フーリエ変換

問題概要

A_{i}\ \ (i=1, 2, \dots, N)、 B_{i}\ \ (i=1, 2, \dots, N)が与えられたとき、

\begin{eqnarray} \sum_{i, j, i+j=k} A_{i}B_{j} \end{eqnarray}

を高速に求めたい。普通に計算すると \mathcal{O}(N^{2})の計算量となるが、これを \mathcal{O}(N\log N)に高速化することを目指す。

問題の詳細は以下を参照 atcoder.jp

フーリエ変換

ある N-1次多項式 F(x) = f(0) + f(1)x + f(2)x^{2} + \dots f(N-1)x^{N-1}があったとして、この多項式の N個の xに対する値 F(x_{0}), F(x_{2}), \dots F(x_{N-1})がわかれば係数が決定できるはずである。適当に x_{0}, x_{1}, x_{N-1}を選んでしまうと F(x_{0}), F(x_{2}), \dots F(x_{N-1})と f(0), f(1), \dots f(N-1)の間の関係式は単純にならないが、1の N乗根を選ぶと直行性により綺麗な関係になるということである。

\xi_{N} \equiv e^{i\frac{2\pi}{N}}と定義すると

\begin{eqnarray} f(x) &=& \frac{1}{N}\sum_{k=0}^{N-1}\hat{f}(\xi_{N}^{-k}) x^{k} \\ \hat{f}(t) &=& \sum_{k=0}^{N-1}f(\xi_{N}^{k}) t^{k} \\ \end{eqnarray}

が成立する。

証明

\begin{eqnarray} f(x) = \frac{1}{N}\sum_{k=0}^{N-1}\hat{f}(\xi_{N}^{-k}) x^{k} \end{eqnarray}

より、

\begin{eqnarray} f(\xi_{N}^{m}) &=& \frac{1}{N}\sum_{k=0}^{N-1} \sum_{k^{'}=0}^{N-1} f(\xi_{N}^{k^{'}}) (\xi_{N}^{-k})^{k^{'}} (\xi_{N}^{m})^{k} \\ &=& \frac{1}{N}\sum_{k=0}^{N-1} \sum_{k^{'}=0}^{N-1} f(\xi_{N}^{k^{'}}) \xi_{N}^{k(m-k^{'})} \\ &=& \frac{1}{N} \sum_{k^{'}=0}^{N-1} f(\xi_{N}^{k^{'}}) \sum_{k=0}^{N-1} \xi_{N}^{k(m-k^{'})} \\ &=& \frac{1}{N} \sum_{k^{'}=0}^{N-1} f(\xi_{N}^{k^{'}}) N\delta (m-k^{'}) \\ &=& f(\xi_{N}^{m}) \end{eqnarray}

よって、 f(\xi_{N}^{m}) \ \ (m=0, 2, \dots , N-1)の異なる Nこの点で関数 fの値が一致することが示されたので、この変換の妥当性が示された。

関数の値の効率の良い求め方。

f(x)は N-1次式なので、 m=0, 1, \dots, N-1の Nこの値について

\begin{eqnarray} f(\xi_{N}^{k}) = f[k] = \hat{f}_{0} + \hat{f}_{1}\xi_{N}^{k} + \hat{f}_{2}(\xi_{N}^{k})^{2} + \dots + \hat{f}_{N-1}(\xi_{N}^{k})^{N-1} \end{eqnarray}

を普通に計算しようとすると \mathcal{O}(N^{2})の計算量となる。これを効率よく計算するため部分問題に分割する。 fの項を偶数部分 f^{(0)}と奇数部分 f^{(1)}に分割すると、それぞれ N/2の次数になるので、

\begin{eqnarray} f^{(0)}[k] &=& \hat{f}_{0} + \hat{f}_{2}\xi_{N/2}^{k} + \hat{f}_{4}(\xi_{N/2}^{k})^{2} + \hat{f}_{6}(\xi_{N/2}^{k})^{3} + \dots \\ &=& \hat{f}_{0} + \hat{f}_{2}(\xi_{N}^{k})^{2} + \hat{f}_{4}(\xi_{N}^{k})^{4} + \hat{f}_{6}(\xi_{N}^{k})^{6} + \dots \\ f^{(1)}[k] &=& \hat{f}_{1} + \hat{f}_{3}\xi_{N/2}^{k} + \hat{f}_{5}(\xi_{N/2}^{k})^{2} + \hat{f}_{7}(\xi_{N/2}^{k})^{3} + \dots \\ &=& \hat{f}_{1} + \hat{f}_{3}(\xi_{N}^{k})^{2} + \hat{f}_{5}(\xi_{N}^{k})^{4} + \hat{f}_{7}(\xi_{N}^{k})^{6} + \dots \\ \end{eqnarray}

したがって、元の定義と見比べれば

\begin{eqnarray} f[k] = f^{(0)}[k] + \xi_{N}^{k} f^{(1)}[k] \end{eqnarray}

と表されることがわかる。

計算量の評価

k=0, 1, \dots, N-1について、 f[k ]を求めるのにかかる計算量を T(N)とする。上で説明した解法により、サイズが半分になった問題 T(N/2)を2つ解き、それを k=0, 1, \dots, N-1について足し合わせればよいので

\begin{eqnarray} T(N) \sim 2T(N/2) + \mathcal{O}(N) \end{eqnarray}

という漸化式が成立する。ここから

\begin{eqnarray} T(N) &\sim& 2T(N/2) + \mathcal{O}(N) \\ &\sim& 2(2T(N/4)+ \mathcal{O}(N/2)) + \mathcal{O}(N) \\ &\sim& 4T(N/4) + 2 \mathcal{O}(N) \\ &\sim& 4(2T(N/8)+ \mathcal{O}(N/4)) + 2 \mathcal{O}(N) \\ &\sim& 8T(N/8) + 3 \mathcal{O}(N) \\ \vdots \\ &\sim& NT(1) + \log N \mathcal{O}(N) \\ &\sim& \mathcal{O}(N\log N) \end{eqnarray}

参考

https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79