math - 多項式を評価しますか？

Question

高速フーリエ変換を使用してn点の多項式を評価するには、なぜO（n log n）時間がかかるのですか？具体的には、多項式A（x）を偶数乗と奇数乗に分割して再帰を使用する分割統治アルゴリズムの実装について話します。

Answer 1

T（n）をFFTアルゴリズムが使用する時間とし、n点で次数nの多項式を評価します。

アルゴリズムが分割されます

A（x）= xB（x ^ 2）+ C（x ^ 2）、

つまり、奇数と偶数の係数の2つの多項式になります。例：3x ^ 3 + 2x ^ 2 + 9x + 7はx（3x ^ 2 + 9）+（2x ^ 2 + 7）に分割されます。

もともと、ポイントa、b、c、dで3x ^ 3 + 2x ^ 2 + 9x+7を計算したかったのです。

^{ここで、点a 2}、b ²、c ²、d2で3x+9と2x+7を計算し^ます。後でそれを組み合わせて、a、b、c、dで3x ^ 3 + 2x ^ 2 + 2x+7の値を取得します。

^{重要なアイデア： 1}の根を使用するため、a ²、b ²、c ²、d2の値の半分は同じです。^{a 2 =} c2およびb2 ⁼ d2^であると仮定します。

^{したがって、ポイントa 2}、b2で3x+ ²と2x+7を計算する必要があります。

これは、サイズNのインスタンスをサイズN / 2とO（N）の後処理の2つのインスタンスに縮小したことを意味します。

FFTはこのプロセスを再帰的に繰り返します。これは、マージソートの場合と同じ漸化式であり、O（N log N）の複雑さです。