假设有 n+1 个实数 a 0 ，a 1 ，…，a n ,和x的序列，要对多项式 P n (x)= a n x n +a n-1 x n-1 +…+a 1 x+a 0 求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，时间复杂度O(n k )。
有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即
P n (x)= a n x n +a n-1 x n-1 +…+a 1 x+a 0 =((…(((a n x +a n-1 )x+a n-2 )x+ a n-3 )…)x+a 1 )x+a 0
这种求值的方法我们称为霍纳法则
比如
P n (x) = 2x 4 -x 3 - 3x 2 + x - 5
P n (x) = x(2x 3 -x 2 - 3x+ 1) - 5
P n (x) = x(x(2x 2 -x - 3)+ 1) - 5
P n (x) = x(x(x(2x -1) - 3)+ 1) - 5
这样时间复杂度就变成O(n)了。
两个计算结果有着巨大的差异