顯示兩個多項式之間的乘法是o（nlogm）？

Question

考慮以下幾點：
兩個多項式，m度的一方和另一方的n度的，我需要顯示它們之間的乘法如何 是o(n*log(m))，當m<n。

比方說，A(x)的程度爲n,B(x)的程度爲m。

我的感覺是這樣的：

1. 我們採取的第一個多項式，姑且稱之爲A(x)，並單獨給m部分，這意味着在總m/n多項式。這將需要o(n)。
2. 取出每個損壞的多項式並用B(x)乘以FFT。
3. 我們將結果存儲在n+m值的數組中。

但從這裏我不知道如何繼續。我會感謝您的幫助，

Answer 1

請參閱Schönhage–Strassen algorithm使用矩陣多項式乘法。