多項式の評価？

Question

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

Answer 1

T（n）をnポイントの次数nの多項式を評価するためにFFTアルゴリズムで使用する時間とします。

アルゴリズムは、2つの多項式に

A（X）= xBの（X^2）+ C（X^2）、

すなわちを分割：奇数と偶数係数。たとえば、3x^3 + 2x^2 + 9x + 7はx（3x^2 + 9）+（2x^2 + 7）に分割されます。

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

今、あなたは、 C、 B、D をポイントで3倍+ 9と2X + 7を計算したいです。後でそれを組み合わせて、a、b、c、dで3x^3 + 2x^2 + 2x + 7の値を取得します。

重要な考え方は：あなたが団結の根、の値の半分を使用しているため、 B、 C、D は同じです。 = c とb = d とします。

だから、 B、ポイントで3倍+ 2と2X + 7を計算する必要があります。

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

FFTはこのプロセスを再帰的に繰り返します。これは、Mergesortと同じ再帰方程式であり、O（N log N）の複雑さです。