给出一个计算输入多项式的算法
an xn+an-1 xn-1+⋯+a1 x+a0
对于 x 的给定值，时间为 Ω(n2) 和 O(n)。
我试图证明这一点，但无法找到合适的算法，任何人都可以帮助我理解这个想法吗？
最佳答案
您可以使用 Horner's Rule在 O(n) 中对其进行评估:
(..( (a_n x + a_(n-1) ) x + a_(n-2) ) x + ... + a_0)。
关于algorithm - 多项式函数的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21657836/