深海游弋的鱼 – 默默的点滴

多项式计算

在计算机科学里，我们会经常遇到一些关于计算多项式的问题，例如计算当 $x = 2$ 时 $2 x^{4} - 3 x^{3} + 5 x^{2} + x - 7$ 的值。我们首先能够想到的方法就是求出每一项的值，然后把它们全部加起来。如果多项式的阶数不高，这种方法完全可行，而且更容易理解，可是如果把这个问题推广到 $n$ 阶，即计算 $a_{n} x^{n} + a_{n - 1} x^{n - 1} + \cdot \cdot \cdot + a_{2} x^{2} + a_{1} x + a_{0}$ 的值，而且当 $n$ 很大时，这种算法就显得力不从心了。

这里以 $2 x^{4} - 3 x^{3} + 5 x^{2} + x - 7$ 为例计算当 $x = 4$ 时的值。下面是直接求解的代码：

def poly_bf(coeffi_list, x):
    degree = len(coeffi_list) - 1  # 最高次项
    result = 0
    for i in range(degree+1):
        coeffi = coeffi_list[i]; poly = 1
        for j in range(degree-i-1, -1, -1):
            poly *= x  # 计算 x^i
        result += coeffi * poly
    return result

				
					
				1
2
3
4
5
6
7
8
9

						def poly_bf(coeffi_list, x):
    degree = len(coeffi_list) - 1  # 最高次项
    result = 0
    for i in range(degree+1):
        coeffi = coeffi_list[i]; poly = 1
        for j in range(degree-i-1, -1, -1):
            poly *= x  # 计算 x^i
        result += coeffi * poly
    return result

					

			

直接求解的方法的复杂度等于多少呢？我们知道，计算机在计算乘法的时候的时间开销要大于加减法的时间开销，所以这里的复杂度大致看做是执行乘法运算的次数。

$T (n) = \sum_{i = 1}^{n} i + 1 = 2 + 3 + \dots + n + 1 = \frac{n (n + 3)}{2} \in Θ (n^{2})$

最后得到时间复杂度为 $Θ (n^{2})$ 。

霍纳法则

霍纳法则（Horner’s rule）可以将上面的多项式转化成下面的形式：

$p (x) = (\dots (a_{n} x + a_{n - 1}) x + \dots) x + a_{0} "$

假设还是计算当 $x = 4$ 时 $2 x^{4} - 3 x^{3} + 5 x^{2} + x - 7$ 的值，我们需要先将其转换为 $x (x (x (2 x - 3) + 5) + 1) - 7$ 的形式，为了更好地呈现每一步的计算过程，我们可以构建出下面的表格：

实现霍纳法则的代码非常简单，只需要用一个循环即可。

def poly_horner(coeffi_list, x):
    degree = len(coeffi_list) - 1  # 最高次项
    result = coeffi_list[0]
    for i in range(1, degree+1):
        result = result * x + coeffi_list[i]
    return result

				
					
				1
2
3
4
5
6

						def poly_horner(coeffi_list, x):
    degree = len(coeffi_list) - 1  # 最高次项
    result = coeffi_list[0]
    for i in range(1, degree+1):
        result = result * x + coeffi_list[i]
    return result

					

			

经过霍纳法则变换的多项式只需要执行 $n$ 次乘法运算便可以得到 $n$ 阶多项式的值，所以复杂度自然就为 $Θ (n)$ 。跟直接求解相比有了明显的提升，根本原因在于我们对问题做了一个变换，使其变得更容易求解。

一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

霍纳法则

多项式计算

霍纳法则

参考链接

发布者

默默

发表回复取消回复

多项式计算

霍纳法则

参考链接

发布者

默默

发表回复 取消回复

发表回复取消回复