给定一个系数向量和一个值，计算多项式的最快方法是什么？
我记得在某处读过（也许有人可以帮助记住在哪里），有一种计算多项式最快的方法。我想起这与 Vietta 公式有关，或者说 0 次方系数是多项式任意因子的 0 次方系数的乘积。
我知道维基百科说这是霍纳的最快评估方案。但我记得你其实根本不用这样评价——它有根源吗？
我所确定的是，有一种计算多项式的方法，当您看到它时，会给您一种“哦，这很聪明”的感觉，但它并不太难，而且有点明显。
有好心人或者聪明人可以帮助我吗？
它的意思是“你可以通过……在 x 处评估 P”，然后有一个非常简单的小事情，实际上可以避免在多项式次数的顺序上进行任何实际的加法和乘法。
I remember reading somewhere (maybe someone can help remember where), that there is a method that is the fastest for evaluating a polynomial. Something reminds me that it had something to do with Vietta's formula, or the fact that the 0-power coefficient is the product of the 0-power coefficients of any factors of the polynomial.
I know wikipedia says it's Horner's scheme for evaluating fastest. But I recall that you actually did not have to evaluate in that way at all - it had something with the roots?
All I know for sure is that there was a method for evaluating a polynomial that has gives you a "oh that is clever" kind of feeling when you see it, but it's not too difficult and is kind of obvious.
Anyone kind or smart enough to help me out?
It is something along the lines of "you can evaluate P at x by ... " and then there is a really simple little thing that actually avoid having to do any real additions and multiplications on the order of the polynomial degree.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您是否多次评估多项式？多项式是不是特别简单？考虑以下多项式：
如果我们想减少计算
f(a)所需的乘法次数，我们可以从 加法链指数：这表明我们可以仅使用 5 次乘法来计算
f(a)。对于具有小系数的固定多项式，这可以是显着的节省。维基百科注释：对于许多
f(a)可以改变的现实情况，另一种方法可能是合适的，但值得注意的是替代解决方案！Are you evaluating the polynomial more than once? Is the polynomial particularly simple? Consider the following polynomial:
If we want to reduce the number of multiplications required to evaluate
f(a)we can compute the minimal addition chain from addition-chain exponentiation:Which shows we can compute the
f(a)using only 5 multiplications. For a fixed polynomial with small coefficients this can be signifigant savings. Wikipeida notes:For many real-world cases where
f(a)can vary another method may be appropriate, but it's worth noting alternate solutions!我认为您正在寻找快速傅里叶变换，看到这个也很好FFT 的 PowerPoint。事实上，当您想要计算 n 个不同点的多项式值时，FFT 非常有用，其时间复杂度为 O(n log n) 并且比 Horner 算法快得多。
FFT 基于单位的 n 次方根的幂，并使用它们之间的关系，因此当您想要计算 n 个不同的点值时，速度非常快。
I think you looking for Fast Fourier Transform it's good too see this PowerPoint on FFT. In fact FFT is useful when you want to calculate polynomial value in n different point which is O(n log n) and very faster than Horner algorithm.
FFT works on power of n'th root of unit, and uses relation between them and because of this is very fast when you want to compute n different points value.