秦九韶算法快速计算多项式的值

抛出问题

给定下列一元3次多项式

f(x)=4x^{3}+3x^{2}+2x^{1}+1x^{0} （1）

计算 f(4) 需要进行总共几次乘法运算，几次加法运算？

由3次推广到一元n次多项式

f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x^{1}+a_{0}x^{0} （2）

计算 f(4) 需要进行总共几次乘法运算，几次加法运算？

朴素算法

以朴素算法求解（1）的话，计算 f(4) 总共需要

(1+2)+(1+1)+1=6 次乘法

1+1+1=3 次加法

以朴素算法求解（2）的话，计算 f(4) 总共需要

[1+(n-1)]+[1+(n-2)]+[1+(n-3)]+...+1

=n+(n-1)+(n-2)+...+1

=\frac{n(n+1)}{2} 次乘法 （3）

n1=n 次加法 （4）

由（3）（4）可知，用朴素算法计算一元n次多项式时，乘法运算的时间复杂度为 O(n^{2}) ,

加法运算的时间复杂度为 O(n) 。当n很小时，乘法的次数尚可接受，当n很大时，乘法的次数将会影响程序的性能。

那么是否存在一种方法可以降低乘法运算的次数呢？是的，就是接下来要介绍的秦九韶算法。

秦九韶算法

一句话概括秦九韶算法是一种将一元n次多项式转换为n个一次式的简化算法。

以（1）为例，运用秦九韶算法

f(x)=4x^{3}+3x^{2}+2x^{1}+1x^{0}

=x(4x^{2}+3x^{1}+2)+1

=x(x(4x+3)+2)+1

计算 f(4) 时，计算最内层括号内一次多项式的值

4x+3=44+3=19

然后由内向外逐层计算一次多项式的值

x19+2=419+2=78

\Rightarrow x78+1=478+1=313

可以看到，一共进行了3次乘法，3次加法。并推出计算（2）时，总共需要至多n次乘法，n次加法。也就是说使用秦九韶算法计算一元n次多项式时，乘法运算的时间复杂度为 O(n) ,加法运算的时间复杂度为 O(n) 。对比朴素算法，大大简化了乘法运算的次数。

程序设计

秦九韶算法作为计算一元n次多项式的最优算法，怎么用代码实现呢？

给定次数和系数就可以唯一确定一个多项式，系数用一个数组存储，数组中的元素下标从 0\sim n ，刚好对应存入 a_{0}\sim a_{n} 。

然后po出（2）的秦九韶方法

f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x^{1}+a_{0}

=(...((a_{n}x+a_{n-1})x+a_{n-2})x+...+a_{1})x+a_{0}

可以发现，每一层的运算都是固定的格式 a_{i}x+a_{i-1} ，所以可以用一个 for 循环实现。

具体实现可参考我上传到GitHub上的代码，初次使用GitHub，还在熟悉ing...

第一次在知乎上发文，在内容上力求循序渐进，从问题导入引出解决办法，这也是我学习该算法时的逻辑顺序。