2つの多項式間の乗算がo（nlogm）であることを示しますか？

Question

を考えると、次の
2つの多項式、度mの一つと程度nの他に、私は示して必要なそれらの間の乗算はo(n*log(m))、m<nですか 。

例えば、A(x)は度がn、B(x)は度がmであるとします。

私の伐採は以下の通りです：

1. 私たちは、第1の多項式を取る、のはA(x)それを呼び出すと、合計でm/n多項式を意味し、m部分にそれを分離してみましょう。これにはo(n)が必要です。
2. 破損した多項式のそれぞれに、を掛けて、FFTを使用します。
3. 結果をn+m値の配列に格納します。

しかし、ここから私はどのように続行するのか分かりません。私はあなたの助けを感謝します

Answer 1

Schönhage–Strassen algorithmを参照してください行列を使用して多項式乗算。