假设有 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)了。
两个计算结果有着巨大的差异