我在书后面列出的这个问题上遇到了一点麻烦，我目前正在准备考试，但我似乎在书中找不到任何关于此的内容。
有人有想法吗？
A real polynomial of degree n is a function of the form f(x)=a(n)x^n+⋯+a1x+a0, where an,…,a1,a0 are real numbers. In computational situations, such a polynomial is represented by a sequence of its coefficients (a0,a1,…,an). Assuming that any two real numbers can be added/multiplied in O(1) time, design an o(n^2)-time algorithm to compute, given two real polynomials f(x) and g(x) both of degree n, the product h(x)=f(x)g(x). Your algorithm should **not** be based on the Fast Fourier Transform (FFT) technique.
请注意，它必须是 small-o(n^2)，这意味着它的复杂性必须是次二次的。
我一直在寻找的明显解决方案确实是 FFT，但我当然不能使用它。我发现了另一种称为卷积的方法，如果将多项式 A 作为信号，将多项式 B 作为滤波器。A 通过 B 产生已被 A“平滑”的移位信号，结果为 A*B。这应该在 O(n log n) 时间内工作。当然，我完全不确定实施。
如果有人对如何实现 small-o(n^2) 实现有任何想法，请分享，谢谢。