假设有n＋2个实数a0，a1，…，an,和x的序列，要对多项式Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，它需要进行n＋(n－1)＋…＋1＝n(n＋１)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０＝((…(((anx＋an－１)x＋an－２)x+ an－3)…)x＋a1)x＋a０，这种求值的安排我们称为霍纳法则。

例如，当x=3时，计算p(x)=2x4－x3＋3x2＋x－5的值。对于多项式p(x)=2x4－x3＋3x2＋x－5，我们按霍纳法则进行变换，有：

p(x)=2x4－x3＋3x2＋x－5

         =x(2x3－x2＋3x＋1)－5

          =x(x(2x2－x＋3)＋1)－5

             =x(x(x(2x－1)＋3)＋1)－5

在实际的操作过程中，为了得到上式，我们没有必要经过上述的特定变换，我们只需要一个该多项式系数的原始列表。我们可以方便地用一个二维表格来帮助我们笔算求出这个多项式的值。该表第一行包含了该多项式的系数（如果存在等于0的系数，也都包含进来），从最高的an到最低的a0。第二行中除了第一个和第二个单元格用来存储x和an外，其它单元格都用来存储中间结果。在作了这样的初始化后，在计算第二行的某一个单元格的值时，用该单元格的前一个单元格乘以x的值再加上该单元格的第一行的系数即可。用这种方式算出的最后一个单元格的值，就是该多项式的值。

系数

a4

a3

a2

a1

a0

2

－1

3

1

－5

x=3

2

3*2－1=5

3*5+3=18

3*18+1=55

3*55－5=160

    所以，P(3)=160。我们拿表格中的单元格和多项式x(x(x(2x－1)＋3)＋1)－5做比较，我们会发现3*2－1=5是2x－1在x=3时的值，3*5+3=18是x(2x－1)＋3在x=3时的值，3*18+1=55是x(x(2x－1)＋3)＋1在x=3时的值，最后3*55－5=160是x(x(x(2x－1)＋3)＋1)－5在x=3时的值。

     二﹑霍纳法则的程序实现

    上述的计算过程我们可以用一个递推的关系表示，即Pi(x)= xPi－1(x)＋an－i，递推的临界值P0(x)= an，其中i=1…n。具体在实现时使用了滚动数组技术。

   算法  Horner(p[0...n], x)

         //用霍纳法则求一个多项式在一个给定点的值

         //输入：一个n次多项式的系数数组p[0...n](从低到高存储），以及一个数字x；

         //输出：多项式在x点的值

         p = p[n];

         for i = n - 1 downto 0 do

             p = x * p + p[i];

         return p;

    滚动数组的作用在于优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

    滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于DP中。

三、霍纳法则的副产品

该算法在计算p(x)在某些点x0上的值时所产生的中间数字，恰好可以作为p(x)除以x-x0的商的系数，而算法的最后结果，除了等于p(x0)外，还等于这个除法的余数。因此，对于我们的例子来说，p(x)=2x4－x3＋3x2＋x－5除以x-3的商和余数分别为2x3＋5x2＋18x+55和160.这种除法算法被称为“综合除法”，要比所谓的“长除法”更方便。