[算法] 秦九韶算多项式（霍纳法则）

目录

• 问题提出

• 常规方法

• 秦九韶的方法

• 小结

1. 问题提出

我们都曾学习过多项式，比如 $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4$ 就是一个一元四次多项式，也可以很容易记得，一元 $n$ 次多项式的通式为$f(x)=a_0+a_1x+a_2x^2+…+a_nx^n$ ，也可以缩略表示为 $f(x)=\sum_{i=0}^na_ix^i$ 。对于这样的一元 $n$ 次多项式，我们要怎样求解？

2. 常规方法

首先我们很容易想到，将多项式拆解计算，举例一元四次多项式，将其拆解，看做为 $f(x)=a_0+a_1 \times x+a_2 \times x \times x+a_3 \times x \times x \times x+a_4 \times x \times x \times x \times x$ 。这样我们需要计算 $0+1+2+3+4=10$ 次的乘法，和4次的加法，得到多项式结果。

推广开来，一元 $n$ 次多项式时，我们需要计算 $0+1+2+…+(n-2)+(n-1)+n=\frac{n(n+1)}{2}$ 次乘法，和 $n$ 次的加法，得到多项式的结果。

那么用代码怎么实现？

很容易地，使用两个for循环，就可以得到想要的结果，这个函数的基本操作为 t = t * x; ，时间复杂度为 $O(n^2)$，计算过程如下：

$$\begin{align*} T(n) &= \sum_{i=0}^{n} \sum_{j=0}^{i}1\\ &= \sum_{i=0}^{n}(i)\\ &= \frac{n \times (n + 1)}{2}\\ &= \frac{1}{2}n + \frac{1}{2}n^2\\ &= O(\frac{\frac{1}{2}n^2}{\frac{1}{2}}) = O(n^2) \end{align*}$$

//c语言
double polynomial(int n, double a[], double x)
{
	double t, result=0;
	int i, j;
	for (i=0; i<=n; i++)
	{
		t = 1;
		for (j=0; j<i; j++)
			t = t * x;
		result = result + a[i] * t;
	}
	return result; 
} 

或者是，将一个for循环改成递归，也可以实现，类似的，可以算出其时间复杂度为 $O(n^2)$。

//c语言
double f(int n, double x)
{
	double result = x;
	if (n == 0)
		return 1;
	else if (n == 1)
		return x;
	else
		return result * g(--n, result);
}
double polynomial( int n, double a[], double x )
{
	double result=0;
	int i;
	for (i=0; i<=n; i++)
	{
		result = result + a[i] * f(i, x);
	}
	return result; 
} 

当然，不管是使用两个for循环，或者是使用递归，都没有办法改变 $O(n^2)$ 的时间复杂度。那么，就没有更简便的方法了吗？

3. 秦九韶的方法

我国古代伟大的数学家秦九韶，就想出了一个办法，用于简化多项式计算，这个方法就叫秦九韶算法，在国际上称为霍纳法则。

以一元四次多项式为例，我们可以将其看为：

$$\begin{align*} f(x)&=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4\\ &=a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4\\ &=a_0+x(a_1x^0+a_2x^1+a_3x^2+a_4x^3)\\ &=a_0+x(a_1+x(a_2x^0+a_3x^1+a_4x^2))\\ &=a_0+x(a_1+x(a_2+x(a_3x^0+a_4x^1)))\\ &=a_0+x(a_1+x(a_2+x(a_3+a_4x))) \end{align*}$$

即先计算最内层多项式的值，再逐一向外层计算，这样我们就只需要进行4次乘法，4次加法，就可以算出一元四次多项式的值。

可以推广开来，带入一元 $n$ 次多项式：

$$\begin{align*} f(x)&=a_0+a_1x+a_2x^2+...+a_nx^n\\ &=a_0x^0+a_1x^1+a_2x^2+...+a_nx^n\\ &=a_0+x(a_1x^0+a_2x^1+...+a_nx^n)\\ &=a_0+x(a_1+x(a_2x^0+...+a_nx^n))\\ &=a_0+x(a_1+x(a_2+...+x(a_{n-1}x^0+a_nx^1))...)\\ &=a_0+x(a_1+x(a_2+...+x(a_{n-1}+a_nx))...) \end{align*}$$

很容易就发现，每一层的运算都是 $a_{i-1}+a_ix$ ，所以可以使用一个for循环实现，将时间复杂度降为 $O(n)$ 。

//c语言
double polynomial(int n, double a[], double x)
{
	double result=a[n];
	int i;
	for (i=n; i>0; i--)
	{
		result = result * x + a[i-1];
	}
	return result; 
} 

4. 小结

本来应该是到第三点就结束了，但是思来想去，还是做个复盘，给自己一个交代。

好久没有写题目了，不记得上次写题在什么时候了。重新捡起来必然是痛苦的，但是收获一定也是让我开心的。那就让这个，数论中基础的秦九韶算法，开启我复健的第一步吧。

虽良宵苦短，但来日方长，少女前进吧！

我的微信公众号：

扫一扫关注我的微信