一个相当普遍的问题，评估 400 到 500 次多项式的最快（就时间复杂度而言）算法是什么。
提前致谢。
问问题
3446 次
2 回答
9
如果您正在谈论多项式的评估，您可能不会比线性时间霍纳方案更快- 除非您有一些特殊情况。
如果您正在谈论多项式的乘法，那么Karatsuba 算法相当容易实现，并且对于该大小而言相当快。我相信基于快速傅里叶变换的算法只有在你有更大的多项式时才值得使用。
于 2009-12-09T21:20:53.713 回答
3
快速傅里叶变换 (FFT) 的修改版本通常为此类问题提供非常好的结果。看看这篇论文，它建议采用混合 FFT 方法。我将通过寻找“快速单变量 FFT”方面的术语来开始您的研究。它还可以帮助您注意，将两个多项式相乘与两个整数相乘本质上是相同的操作。
于 2009-12-09T21:09:14.953 回答