秦九韶算法，是中国南宋时期的数学家秦九韶提出的一种多项式简化算法，在西方被称作霍纳算法，
主要用于简化对于一般n次多项式的计算步骤。
我们知道，对于常规的求多项式 f ( x ) f(x) f(x)计算结果的思路是逐项系数与带次数的 x x x项相乘最后相加求和。
考虑题目：求多项式 f ( x ) = a 0 x 0 + a 1 x 1 + . . . + a n x n f(x)=a_0x^0+a_1x^1+...+a_nx^{n} f(x)=a0x0+a1x1+...+anxn的值，其中 a [ ] a[ ] a[]数组按 0 0 0到 n n n顺序存储系数， n n n为多项式阶数
使用代码实现的思路如下：
// n为多项式阶数，a为系数
double f2(int n, double a[], double x){
double res = 0.0;
for(int i = 0;i < n+1;i++) {
// 逐项相乘后累加到结果res上
res += a[i] * pow(x, i);
}
return res;
}
这种方式实现的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，在n比较大情况下的计算会比较耗时，这里我们可以考虑使用秦九韶算法对时间上进行简化。
所谓秦九韶算法，通俗来讲，即对于从最低次的多项式项开始，逐次进行类似提取公因式的步骤。因为我们会发现，对于一个多项式的最高次项如 k x n kx^n kxn来说，相当于它可以提取 n n n次 x x x，以此类推，我们可以对于多项式的高次项反复进行提取公因式 x x x，直至无法再进行提取操作，用公式的形式进行直观表述如下：
f
(
x
)
=
a
n
x
n
+
a
x
−
1
x
n
−
1
+
.
.
.
+
a
1
x
+
a
0
f(x)=a_nx^n+a_{x-1}x^{n-1}+...+a_1x+a_0
f(x)=anxn+ax−1xn−1+...+a1x+a0
=
(
a
n
x
n
−
1
+
a
n
−
1
x
n
−
2
+
.
.
.
+
a
2
x
+
a
1
)
x
+
a
0
=(a_nx^{n-1}+a_{n-1}x^{n-2}+...+a_2x+a_1)x+a_0
=(anxn−1+an−1xn−2+...+a2x+a1)x+a0
=
(
(
a
n
x
n
−
2
+
a
n
−
1
x
n
−
3
+
.
.
.
+
a
3
x
+
a
2
)
x
+
a
1
)
x
+
a
0
=((a_nx^{n-2}+a_{n-1}x^{n-3}+...+a_3x+a_2)x+a_1)x+a_0
=((anxn−2+an−1xn−3+...+a3x+a2)x+a1)x+a0
=
(
.
.
.
(
a
n
x
+
a
n
−
1
)
x
+
a
n
−
2
)
x
+
.
.
.
+
a
1
)
x
+
a
0
=(...(a_nx+a_{n-1})x+a_{n-2})x+...+a_1)x+a_0
=(...(anx+an−1)x+an−2)x+...+a1)x+a0
实现代码及注释：
C/C++ version：
// 我们从上述最下面一步公式开始看
// 整体思路可以看作是从最内层括号a_n * x + a_{n-1}部分每次乘以x后加上后面一项，然后反复步骤
double f(int n, double a[], double x){
double res = a[n] * x;
for(int i = n-1;i > 0;i--) {
// 每次循环都是先累加后面一项再乘以x
res += a[i];
res *= x;
}
// 记得加最后一项a_0
res += a[0];
return res;
}
Python version：
def algorithm(n, a, x):
res = a[n] * x
for i in range(n-1, 0, -1):
res = (res + a[i]) * x
res += a[0]
return res
观察分析得出，使用秦九韶算法计算多项式的时间复杂度为 O ( n ) O(n) O(n)。
参考资料：[1]:https://baike.baidu.com/item/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95/449196?fr=ge_ala
