在特定值處評估多項式的​​最快方法

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方法存在，但更復雜。