23. 霍纳法则（多项式求值快速算法）

一. 概念引入

1.定义

（1）x 的 n 次多项式： P(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀。（其中 x 是底数， n 是指数， a_i 是每一项前面的系数， 0 ≤ i ≤ n ，并且最高次项前面的系数不为 0 ）

2. 实例分析

（1）求 xⁿ 的方法：

xⁿ = x · x · … · x （共 n 个 x ），显然，式子中执行了 n - 1 次乘法。

取 x = 2, n = 3 时，该项为 2³ = 2 × 2 × 2，可以看出，执行了 2 次乘法。

（2）求 x 的 n 次多项式的方法：

假设有多项式 P(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀。先看第一项 a_nxⁿ ，其中 xⁿ 执行了 n - 1 次乘法，再与 a_n相乘，共执行 n 次乘法。其余各项同理。

取 x = 2, n = 4, 系数为 1 时， P(2) = 2⁴ + 2³ + 2² + 2¹ + 1

二. 多项式求值常规算法

继续以上例来说明问题：取 x = 2, n = 4，系数为 1 时， P(2) =2⁴ + 2³ + 2² + 2¹ + 1。

当我们用正常思路去计算，即先算第一项，再算第二项，直到算出每项结果，最后将各项结果相加。先算第一项： 2 × 2 × 2 × 2 ，再算第二项： 2 × 2 × 2，再算第三项： 2 × 2。该算法的时间复杂度是 O(n²)。我们可以发现，其中有很多重复步骤。第一项已经做完了大部分工作，其余项为什么要把第一项的劳动成果弃之不用呢？

三. 霍纳法则

霍纳将多项式进行变形：P(x) = a₃x³ + a₃x² + a₁x + a₀ → P(x) = x ( x ( x ( a³ ) + a² ) + a¹ ) + a⁰ ，这样执行多项式求值，每一次的结果都能得到充分的利用，不难看出，霍纳算法的时间复杂度是 O( n )

四. 代码实现

1. 常规算法

这里我手动实现了一个函数 cal_power，用于计算 x 的 n 次方。

 1 int cal_power(int x, int n) {
 2     int product = x;
 3     for (int i = 0; i < n - 1; ++i) {
 4         product *= x;
 5     }
 6 
 7     return product;
 8 }
 9 
10 int cal_ploy (vector<int> &coefficient, int x, int n) {
11     int sum = coefficient[ n ];
12     for (int i = 0; i < n; ++i) {
13         int item = coefficient[ i ] * cal_power(x, n - i);
14         sum += item;
15     }
16 
17     return sum;
18 }

2.霍纳法则

1 int honour_rule(vector<int> &coefficient, int x, int n) {
2     int sum = coefficient[0];
3     for (int i = 1; i <= n; ++i) {
4         sum = x * sum + coefficient[i];
5     }
6 
7     return sum;
8 }

3.测试

 1 int main() {
 2     int x, n, result;
 3     cout << "Enter x, n : ";
 4     cin >> x >> n;
 5     vector<int> coefficients;
 6 
 7     for (int i = 0; i <= n; ++i) {
 8         int current_num;
 9         cout << "coefficient " << (i + 1) << " : ";
10         cin >> current_num;
11         coefficients.push_back(current_num);
12     }
13 
14     result = cal_ploy(coefficients, x, n);
15     cout << "regular sum = " << result << endl;
16 
17     result = honour_rule(coefficients, x, n);
18     cout << "honour rule sum = " << result << endl;
19 
20     cout << "Done." << endl;
21 
22     return 0;
23 }

其中需要说明几点：

第一，代码中没有错误处理，边界检查，默认输入没有问题，这样做只是为了清楚地说明算法思路，略去了算法无关的内容，但是实际操作中，这些代码必不可少。

第二，用 vector 来保存系数，在输入时，按照表达式的系数顺序输入即可，不用从后往前输入。

23. 霍纳法则（多项式求值快速算法）

相关推荐