محاسبه‌ی مقدار چند‌جمله‌ای

به دنبال راهی با کد کوتاه، عملیات کم و فهم راحت هستیم. در زیر به یک روش با تعداد عملیات $۲n$ میپردازیم.

فرض کنید ضرایب یک چند جمله‌ای را به ترتیب به صورت $a_0, a_1, ..., a_n$ به شما داده اند که $a_i$ ضریب جمله‌ی $x^i$ می‌باشد. به ازای یک $x$ خاص، مقدار این چند‌جمله‌ای را محاسبه کنید.

$a_0$ را از آرایه حذف کنید و فرض کنید آرایه شما به شکل زیر است: $$a_1, a_2, ..., a_n$$ که $a_i$ ضریب جمله‌ی $x^{i-1}$ است. حال به صورت استقرایی مقدار $p$ را برابر با جواب چند‌جمله‌ای به ازای آرایه بالا در نظر بگیرید. اکنون جواب شما به ازای آرایه‌ی اصلی برابر است با: $$p * x + a_0$$

واضح است که پیچیدگی این الگوریتم از $O(n)$ می‌باشد.

‌‌horner.cpp

#include <iostream>
using namespace std;
const int maxn = 1000 * 1000 + 10;
int a[maxn];
int main() {
    int n, x;
    cin >> n >> x;
    for(int i=0;i<=n;++i)
        cin >> a[i];
 
    int p = 0;
    for(int i=n;i>=0;--i)
       p = p * x + a[i];
 
    cout << p << endl;
 
    return 0;
}

• http://en.wikipedia.org/wiki/Horner%27s_method