アルゴリズム学習のHoner's Rule

The usual way to evaluate such polynomials is to use Horner's rule, which is an algorithm to compute the summation without requiring the computation of arbitrary powers of x.
Horner's Ruleは多項式の和を求めるために使用され、その主な利点は降格演算であり、べき乗演算を乗算と加算演算に変えることである.リンク:Horner's Rule

int Horner(int a[], unsigned int n, int x)
{
    int result = a[n];
    for (int i = n - 1; i >= 0; --i)
        result = result * x + a[i];
    return result;
}

アルゴリズム解析:有効演算コード3行目から6行目
row 3  : 3 * T(fetch) + T[.] + T(store)
注意:配列要素の値取り操作は事実上4つのステップを経て、配列の最初のアドレスを取得し、2つは下付きの値を取得し、3つは取得する要素のアドレスT[.]を計算し、要素の値を4つ取ります.
row 4a : 2 * T(fetch) + T(-) + T(store) 
row 4b : ( 2 * T(fetch) + T(<)) * (n + 1)
row 4c : ( 2 * T(fetch) + T(-) + T(store)) * n
row 5  : ( 5 * T(fetch) + T[.] + T(*) + T(+)+ T(store)) * n
row 6  : T(fetch) + T(return)
注意:関数呼び出しの時間は呼び出し元側で計算され、関数が返す時間は変調された関数のオーバーヘッド全体に配置されます.
上記の分析から分かるように、
1,このアルゴリズムの時間的複雑さはT(n),線形関係である.
2,このアルゴリズムの核心思想は蓄積であり,前回の反復の結果を直接次の反復に入れ,演算に関与する.