特定の値で多項式を評価する最速の方法

Question

与えられた次数の多項式と既知の係数を（順番に）評価する最も速いアルゴリズムは何ですか？ （C++/Cで）上記のコードの改善の推奨事項も大歓迎ですので、私は初心者です

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))); 
    } 
} 

： は、私はそれを次の方法を実行しようとしました。多項式を評価する

Answer 1

あなたの評価は、再帰的な複雑性を有する

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

場合のn個の電源の全体的なT（N）= 2N-2の乗算（その結果、唯一の乗算、プラスサブアレイの構築のためのいくつかのオーバーヘッドを数えます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の方法が存在しますが、より複雑です。