به دنبال راهی با کد کوتاه، عملیات کم و فهم راحت هستیم. در زیر به یک روش با تعداد عملیات ۲n میپردازیم.
فرض کنید ضرایب یک چند جملهای را به ترتیب به صورت a0,a1,...,an به شما داده اند که ai ضریب جملهی xi میباشد. به ازای یک x خاص، مقدار این چندجملهای را محاسبه کنید.
a0 را از آرایه حذف کنید و فرض کنید آرایه شما به شکل زیر است: a1,a2,...,an که ai ضریب جملهی xi−1 است. حال به صورت استقرایی مقدار p را برابر با جواب چندجملهای به ازای آرایه بالا در نظر بگیرید. اکنون جواب شما به ازای آرایهی اصلی برابر است با: p∗x+a0
واضح است که پیچیدگی این الگوریتم از O(n) میباشد.
#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; }