روش هورنر

یک الگوریتم بدیهی برای اینکه مقدار این چند جمله‌ای را در نقطه‌ای مانند ${\displaystyle x=x_0}$

Naive-Poly-Eval(A : Poly, x)
 y = ۰
 for k = ۱ to length(A)
  do p = ۱
     for j = ۱ to k
       do p = p*x
     y = y + A[k]*p
 return y

لازم به توضیح است که در شبه کد بالا، A عنوان آرایه‌ای است که ضرایب چندجمله‌ای را در خودش نگه می‌دارد.

تحلیل

نگاهی مختصر به تحلیل این الگوریتم می‌اندازیم. مشخص است که حلقه داخلی بیشترین زمان اجرای را دارد و زمان اجرای کل الگوریتم هم از تتا این زمان اجرا خواهد بود. بنابراین با جمع زدن تعداد دفعات اجرای حلقه داخلی به زمان اجرای ${\displaystyle n^2}$

با کمی دقت در می‌یابیم، این زمان اجرای بالا از این جهت ایجاد می‌شود که ما همیشه برای محاسبهٔ توان n ام ${\displaystyle x_0}$

بنابراین یک ایده برای اینکه الگوریتم را بهتر کنیم این است که همیشه مقدار توان محاسبه شده یک مرحله قبل را نگه داریم تا توان مرحله کنونی را فقط با یک عمل ضرب بدست آوریم. در نتیجه زمان اجرای الگوریتم خطی می‌شود که کارا تر از الگوریتم قبلی است.

ویلیام جورج هورنر با در نظر گرفتن همین ایده پیاده‌سازی دیگری از این الگوریتم را ارائه می‌کند، در ادامه شبه کد این الگورتم آمده‌است:

Horner-Poly-Eval(A : Poly, x)
 y = ۰
 k = n : length(A)
 while k>= ۰
   do y = A[k] + x*y
      k = k - ۱
 return y

روند اجرای الگوریتم هورنر

به روند اجرای این الگوریتم نگاهی دقیق تر می‌اندازیم.

ابتدا چندجمله‌ای را به صورت زیر ساده می‌کنیم:

${\displaystyle P(x)=a_0+x(a_1+x(a_2+...+x(a_{n-1}+x{a}_n)))}$

تا اینجا احتمالاً مشخص شده که این الگوریتم چه طوری عمل می‌کند.

برای روشن شدن قضیه به مقدار y در ابتدای حلقه نگاه می‌اندازیم:

۱ y = ۰
۲ y = A[n]
۳ y = A[n-۱] + y*x
4 y = A[n-۲] + y*x
    .
    .
    .
n y = A[۰] + y*x

تحلیل

برای تحلیل این الگوریتم در نظر داشته باشید فقط یک حلقه وجود دارد که به اندازهٔ طول آرایه A تکرار می‌شود. دستورهای داخل حلقه از O(۱) هستند. بنابراین این الگوریتم هم خطی است.

• چندجمله‌ای
• روش نیوتن رافسون

• بهزاد خداکرمی-الیاس هنگامیان اصل (۱۳۸۶)، «۱»، آنالیز عددی ۱ و جبر خطی، آزاده، ص. ۱۷، شابک ۹۷۸-۹۶۴-۵۰۱-۲۴۲-۵
• محمد قدسی (۱۳۸۸)، «۳»، داده ساختارها و مبانی الگوریتم‌ها، موسسه فرهنگی فاطمی، ص. ۶۳، شابک ۹۷۸-۹۶۴-۳۱۸-۵۴۹-۷
• http://en.wikipedia.org/wiki/Horner_scheme