霍纳法则

多项式计算

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

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

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

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

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

霍纳法则

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

$p(x)=(\cdots(a_nx+a_{n-1})x+\cdots)x+a_0"$

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

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

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

参考链接