multiplication - 评估大多项式的最快算法

Question

一个比较笼统的问题是，用最快的算法（在时间复杂度方面）评估阶次为400到500的多项式的算法是什么。

提前致谢。

Answer 1

如果您要讨论多项式的求值，那么您可能不会比线性时间Horner scheme快-除非您有一些特殊情况。

如果您在谈论多项式的乘法，则Karatsuba algorithm相当容易实现，并且对于该大小而言非常快。我相信，只有在拥有较大的多项式的情况下，基于快速傅立叶变换的算法才值得使用。