Показать, как умножение между двумя полиномами равно 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 для полиномиального умножения с использованием матриц.