多项式与霍纳法则

多项式求值 $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{3}x^{3}+a_{2}x^{2}+a_{1}x$ ，

在多项式的计算中通常乘法比加法慢。因此，乘法是主导的基本操作。假设有一个次数为 $n$ 的多项式，并且各项系数均不为 0。

常规解法

使用常规解法就必须求下列各幂的值。

x^n,\;x^{n-1},\;x^{n+2},\;x^{n-3},\;...\;,\;x^3,\;x^2,\;x^1

第一项执行 $n-1$ 次乘法，第二项是 $n-2$ 以此类推，执行乘法的总数是

(n-1)+ (n-2) + (n-3) + ... + 3 + 2 + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}

除常数外，每项需要与系数的一次乘法，总共是 $n$ 次，因此总的乘法次数是

\frac{n^2}{2} - \frac{n}{2} + n = \frac{n^2}{2} + \frac{n}{2}

根据上面的步骤推导出计算多项式的算法的复杂度为 $O(n^2)$

使用霍纳法则（Horner's method）

霍纳法则（Horner's method）是一种高效的多项式计算方法，用于在给定点快速计算多项式的值。它将多项式计算的时间复杂度从 $O(n^2)$ 降低到 $O(n)$ 。

霍纳法则将其重写为嵌套形式：

P(x) = a_0 + x(a_1 + x(a_2 + \dots + x(a_{n-1} + x\cdot a_n) \dots ))

信息

该算法最早由南宋数学家秦九韶创造，所以又称秦九韶算法。准确来说就应该称为秦九韶算法

南宋数学家秦九韶将贾宪的增乘开方术推广，以求解任意高次方程的实数根的数值解。秦九韶的《数书九章》详细叙述用秦九韶算法求解二十六个二次到十次方程的的实数根的数值解，其中包含二十个二次方程，一个三次方程，四个四次方程和一个十次方程。其中有些得到精确解；多数得近似解。

19世纪初，英国数学家威廉·乔治·霍纳重新发现并证明，后世称作霍纳算法（Horner's method、Horner scheme）。但是，19世纪英国传教士伟烈亚力 Alexander Wylie. (1815–1887) 最早对霍纳的发明权提出质疑。此后，日本数学史家三上义夫在《中日数学史》一书中在详述秦九韶的正负开方术后写道：“谁能否认，霍纳的辉煌方法，至少在早于欧洲六百年之前，已经在中国运用了。”

霍纳在1819年发表的《解所有次方程》论文中的算例，其算法程序和数字处理都远不及五百多年前的秦九韶有条理；秦九韶算法不仅在时间上早于霍纳，也比较成熟。

霍纳法则的步骤

从最高次项开始，将多项式的系数依次乘以 $x$ 并累加。
重复上述步骤，直到处理完所有系数。

示例

假设我们要计算多项式 $P(x) = 2x^3 + 3x^2 + 4x + 5$ 在 $x=2$ 处的值。

可以将多项式写为嵌套形式： $P(x) = 5 + x(4 + x(3 + x\cdot 2))$

按照霍纳法则计算：

步骤 1: 结果 = 2 × 2 + 3 = 7
步骤 2: 结果 = 7 × 2 + 4 = 18
步骤 3: 结果 = 18 × 2 + 5 = 41

所以 $P(2) = 41$

使用霍纳法则重写多项式后，只需要进行 3 次乘法运算。

参考资料

Mark Allen Weiss. 《数据结构与算法分析（Java语言描述符）》. 机械工业出版社. 2008: P22-P42
维基百科. 秦九韶算法.
维基百科. 增乘开立方术.

常规解法​

使用霍纳法则（Horner's method）​

参考资料​

常规解法

使用霍纳法则（Horner's method）

参考资料