分割統治法

質問

分割統治法の練習問題なのですが
n=2^k-1のとき、n次の多項式の積はΘ(n^log3)で求められるとき、どのようなアルゴリズムであるか？
というものです。ちなみに底は2です。

１次の多項式の掛け算の場合、通常４つの乗算を計算すれば係数は求まりますが、(a+c)(c+d)という乗算を用いると3つの乗算で出来るということを使うらしいのですが。確かにこの場合、簡単に3つの乗算と減算でできますが、どのように適当したらいいのでしょうか・・・。

回答No.1

rinkun

Θ(n^log3)は、Ｏ(n^log3)の積もりかな。ＯはOrderの意味だからシータなんかで置き換えちゃ拙いよ。

n=2^k-1だからn次多項式は2^k個の項を持つわけだ。この項を適当に半分に分けていくと、1次多項式を3乗算で計算できるのと同様に、(n-1)/2次多項式[2^(k-1)個の項を持つ]の乗算3つでn次多項式を計算できる。これを再帰的に適用すれば最終的には1次多項式にできる。
具体的な多項式の分解方法(簡単に思いつくだけで2つはある)とオーダー計算の詳細は自分でやってくれ。