2025年【杂项】多项式秦九韶算法

科技前沿 • 2025-01-15 09:16 • 阅读 43

大家好，我是讯享网，很高兴认识大家。

秦九韶算法，是中国南宋时期的数学家秦九韶提出的一种多项式简化算法，在西方被称作霍纳算法，
主要用于简化对于一般n次多项式的计算步骤。

我们知道，对于常规的求多项式 $f (x)$ 计算结果的思路是逐项系数与带次数的 $x$ 项相乘最后相加求和。

考虑题目：求多项式 $f(x)=a_0x^0+a_1x^1+...+a_nx^{n}$ 的值，其中 $a []$ 数组按 $0$ 到 $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)$ ，在n比较大情况下的计算会比较耗时，这里我们可以考虑使用秦九韶算法对时间上进行简化。

所谓秦九韶算法，通俗来讲，即对于从最低次的多项式项开始，逐次进行类似提取公因式的步骤。因为我们会发现，对于一个多项式的最高次项如 $kx^n$ 来说，相当于它可以提取 $n$ 次 $x$ ，以此类推，我们可以对于多项式的高次项反复进行提取公因式 $x$ ，直至无法再进行提取操作，用公式的形式进行直观表述如下：

讯享网

$f(x)=a_nx^n+a_{x-1}x^{n-1}+...+a_1x+a_0$
$a_nx^{n-1}+a_{n-1}x^{n-2}+...+a_2x+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$
$a_nx+a_{n-1})x+a_{n-2})x+...+a_1)x+a_0$

实现代码及注释：

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)$ 。

参考资料：[1]:https://baike.baidu.com/item/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95/?fr=ge_ala

2025年【杂项】多项式秦九韶算法

C/C++ version：

Python version：

相关推荐