-
روش هورنر
روش هورنر روشی کارامد برای محاسبه مقدار یک چندجمله ای در نقطه مورد نظر می باشد.
توصیف الگوریتم:
چند جمله ای زیر را در نظر بگیرید
http://upload.wikimedia.org/math/2/8...b1310fa518.png
کهhttp://upload.wikimedia.org/math/2/2...09cb82663d.png
اعداد حقیقی هستند. می خواهیم چند جمله ای را به ازای مقادیر خاص x مثل x0 را پیدا کنیم.
برای این منظور دنباله های زیر را تعریف می کنیم:
http://upload.wikimedia.org/math/1/e...1c28b6c80d.png
آنگاه b0 مقدار ( f(x0 است.
یاد آوری می کنیم که چند جمله ای می تواند اینگونه نوشته شود:
http://upload.wikimedia.org/math/8/4...28a9ccd87a.png
بنابر این:
http://upload.wikimedia.org/math/8/0...4943611467.png
الگوریتم بدیهی برای محاسبه مقدار چندجمله ای در نقطه مورد نظر
یک الگوریتم بدیهی برای اینکه مقدار این چند جمله ای را در نقطه‌ای مانند x = x0 به دست آوریم، این است که هر جملهٔ این چندجمله ای را مجزا حساب کرده وهمه را با هم جمع کنیم. در ادامه شبه کد این الگوریتم آمده است:
کد:
Naive-Poly-Eval(A : Poly, x)
y = 0
for k = 1 to length(A)
do p = 1
for j = 1 to k
do p = p*x
y = y + A[k]*p
return y
لازم به توضیح است که در شبه کد بالا A به عنوان آرایه ای است که ضرایب چندجمله ای را در خودش نگه می دارد.
تحلیل
خب نگاهی مختصر به تحلیل این الگوریتم می اندازیم. مشخص است که حلقه داخلی بیشترین زمان اجرای را دارد و زمان اجرای کل الگوریتم هم از تتا این زمان اجرا خواهد بود. بنابراین با یه جمع زدن تعداد دفعات اجرای حلقه داخلی به زمان اجرایی معادل n2 می رسیم. که زمان اجرای به نسبت زیادی هست. باید ببینیم آیا راهی برای بهتر کردن الگوریتم هست یا نه؟
یده بهینه کردن این الگوریتم
با کمی دقت در می یابیم، این زمان اجرای بالا از این جهت ایجاد میشود که ما همیشه برای محاسبهٔ توان n ام x0 واقعا n بار عمل ضرب را انجام می دهیم. بدون توجه به اینکه ما می توانیم با انجام دادن فقط یک عمل ضرب این توان را از توان n-1 آن بدست آوریم.
بنابراین یک ایده برای اینکه الگوریتم را بهتر کنیم این است که همیشه مقدار توان محاسبه شده یک مرحله قبل را نگه داریم تا توان مرحله کنونی را فقط با یک عمل ضرب بدست آوریم. این طوری زمان اجرای الگوریتم خطی می شود که بسیار کارا تر از الگوریتم قبلی هست.
ویلیام جورج هورنر با در نظر گرفتن همین ایده پیاده سازی دیگری از این الگوریتم را ارائه می کند، در ادامه شبه کد این الگورتم آمده است:
کد:
Horner-Poly-Eval(A : Poly, x)
y = 0
k = n : length(A)
while k >= 0
do y = A[k] + x*y
k = k - 1
return y
