对于一个普通多项式，有两种表示方法

$$\begin{array}{rl}f(x)& =a_0+a_{1}x+...+a_{n-1}{x}^{n-1}+a_n{x}^n\\ f(x)& =a_0+x(a_1+x(a_2+...+x(a_{n-1}+x{a}_n)))\text{,秦九韶公式}\end{array}$$

显然在计算过程中，由于秦九韶公式充分利用了上一步的计算结果，每次迭代只需要计算一次乘法和一次加法，避免了乘方运算的重复计算，大大缩短了计算时间。

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cmath>
#define MAXN 1e7
using namespace std;

double a[10] = {1,2,3,4,5,6,7,8,9,10};

double fun1(int x){
    double p = a[9];
    for(int i = 9;i>=0;i--){
        p = a[i-1] + x*p;
    }
    return p;
}

double fun2(int x){
    double ans = a[0];
    for(int i = 1;i<10;i++){
        ans += a[i]*pow(x,i);
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    clock_t start,end;
    start = clock();
    for(int i = 0;i<MAXN;i++){
        fun1(1.1);
    }
    end = clock();
    cout << fixed << setprecision(10) << (double)(end-start)/CLOCKS_PER_SEC/MAXN << endl;//强转类型确保计算结果带小数

    start = clock();
    for(int i = 0;i<MAXN;i++){
        fun2(1.1);
    }
    end = clock();
    cout << fixed << setprecision(10) << (double)(end-start)/CLOCKS_PER_SEC/MAXN << endl;
    return 0;
}

多项式加法运算

通过链表存储多项式，通过双指针的方式将结果写进一个新的链表中，得到结果多项式。