在特定值处评估多项式的​​最快方法

Question

评估给定度数的多项式和已知系数（按顺序）的最快已知算法是什么？ 我试着做以下方式：

long long int evaluatepoly(long long int* coeffa0,long long int degree,long long int x) 
{ 
/*coeffa0 is the coeffecient array in order x^0,x^1,x^2....degree->degree of polynomial 
    and x is the value where the polynomial is to be evaluated*/ 
    if(degree==1) 
    { 
    return (coeffa0[0] + (coeffa0[1])*x); 
    } 
    else if(degree==0) 
    return coeffa0[0]; 
    else{ 
    long long int odd,even,n=degree; 
    if(degree%2==0){ 
     odd=(n/2); 
     even=(n/2)+1; 
    } 
    else{ 
     odd=(n+1)/2; 
     even=(n+1)/2; 
    } 
    long long int oddcoeff[odd],evencoeff[even]; 
    int i=0; 
    while(i<=degree) 
    { 
     if(i%2==0) 
     evencoeff[i/2]=coeffa0[i]; 
     else 
     oddcoeff[i/2]=coeffa0[i]; 
     i++; 
    } 
    int y=x*x; 
    return (evaluatepoly(evencoeff,(even-1),y) + x*(evaluatepoly(oddcoeff,(odd-1),y))); 
    } 
} 

我是初学者所以在改善上面的代码是建议也欢迎（在C/C++）。

Answer 1

你的评价具有递归复杂

T(2n)=2*T(n)+2 

如果只计算乘法，再加上一些开销子阵列的结构，从而在整体上T（N）= 2N-2个乘法（对于n次幂2）。 （错误命名的）Horner方法使用n-1次乘法运算。

Answer 2

一个非常简单的，以评估多项式比较快的方法是使用的事实，你增加指数与每个术语：

int polynomial(int* coefs, int deg, int x) { 
    int factor = 1, result = 0; 
    for(int term = 0; term <= deg; term++) { 
     result += coefs[term] * factor; 
     factor *= x; 
    } 
    return result; 
} 

上面的代码在多项式程度的线性时间复杂度。考虑这个伪代码，我没有编译它。希望能帮助到你！

Faster方法存在，但更复杂。