秦九韶算法

本章涉及知识点

1、多项式计算式

2、如何在1毫秒内计算出多项式结果

3、秦九韶算法

4、改善程序算法

一、多项式计算式

假设我们有如下计算式，求当x=2时f(x)的值

一元n次多项式

这是一个一元n次多项式，涉及到的四则运算包含加法和乘法，我们的需求是尽可能在1毫秒之内计算出其结果

二、如何在1毫秒内计算出多项式结果

直观上想到的第一种方法就是直接带入x=2运算即可，下面为了演示计算的消耗时间，我们用JavaScript语言作为计算演示（当然，不限于任何语言来演示）

为了尽快计算结果，我们可以分析出程序要尽量减少调用API

为此我们编写出如下程序

直接计算f(x)

代码中除了调用console.log方法耗时，并没有调用其余API函数，我们带入x=2直接计算出结果

直接计算多项式结果

可以看到程序运行大约2毫秒，多运行几次，大概需要2~3毫秒之间，偶尔会出现1毫秒，显然不符合我们的需求

那么问题出在哪里呢？我们已经尽可能减少API的调用，所以我们需要聚焦到f(x)多项式本身

观察f(x)，发现这个多项式进行了4次加法操作，那么乘法的次数呢？进行了7+6+4+1=18次乘法，在计算机里，乘法的本质就是加法，且乘法的耗时要大于加法，那么自然而然我们只有降低乘法的次数，才能提高f(x)的计算速度

三、秦九韶算法

我们抽象出一般的一元多项式

一般化一元n次多项式

容易计算出，f(x)进行了n次加法计算，进行的乘法计算次数为等差数列的求和：

乘法计算次数

显然，f(x)乘法的计算次数要远远大于加法的计算次数，我们需要利用我国南宋时期著名数学家秦九韶算法进行多项式等效变形

秦九韶算法

秦九韶算法使用提取x公因式和整体换元法来等效的变形了f(x)，而经过算法变形之后，我们可以看到f(x)的乘法计算次数降低到了n次

这样对于n次多项式的求值为题，就转化为n个一次多项式的求值问题，妙哉！

四、改善程序算法

我们明白了需要问题的关键是要降低乘法计算次数，利用秦九韶算法，我们做如下变形f(x)

秦九韶算法变形f(x)

修改程序为

秦九韶算法计算f(x) 秦九韶算法结果

减少了乘法计算次数，程序的计算速度也提高了

最后我们可以根据秦九韶算法总结出：对于一个n次多项式，至多做n次乘法和n次加法