我在书后面列出的这个问题上遇到了一些麻烦，我目前正在准备考试，但我似乎无法在书中找到与此相关的任何内容。
有人知道吗？
n 次实多项式是 f(x)=a(n)x^n+⋯+a1x+a0 形式的函数，其中 an,...,a1,a0 是实数。在计算情况下，这样的多项式由其系数序列 (a0,a1,…,an) 表示。假设任意两个实数可以在O(1)时间内相加/相乘，设计一个o(n^2)时间的算法来计算，给定两个n次实数多项式f(x)和g(x)，乘积 h(x)=f(x)g(x)。您的算法不应**基于快速傅立叶变换 (FFT) 技术。
请注意它需要小-o(n^2)，这意味着它的复杂度必须是次二次的。
我找到的最明显的解决方案确实是 FFT，但我当然不能使用它。我发现了另一种称为卷积的方法，如果您将多项式 A 作为信号，将多项式 B 作为滤波器。 A 通过 B 产生一个移位信号，该信号已被 A“平滑”，结果为 A*B。这应该在 O(n log n) 时间内工作。当然，我完全不确定实现情况。
如果有人对如何实现 small-o(n^2) 实现有任何想法，请分享，谢谢。
最佳答案
small-o :f(x) = o(g(x)) 等价于 lim x -> inf f(x)/g(x) = 0。
使用 Karatsuba algorithm
关于algorithm - 多项式乘法的 Small-o(n^2) 实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13345839/