科抖ECommerce2019-03-16 15:09:42

秦九韶演算法是中國南宋時期的數學家秦九韶提出的一種多項式簡化演算法。在西方被稱作霍納演算法（horner algorithm或horner scheme），是以英國數學家威廉·喬治·霍納命名的。

把一個n次多項式f（x）=a［n］x^n+a［n-1］x^（n-1）+……+a［1］x+a［0］改寫成如下形式：

f（x）=a［n］x^n+a［n-1］x^（n-1））+……+a［1］x+a［0］

=（a［n］x^（n-1）+a［n-1］x^（n-2）+……+a［1］）x+a［0］

=（（a［n］x^（n-2）+a［n-1］x^（n-3）+……+a［2］）x+a［1］）x+a［0］

=……

=（……（（a［n］x+a［n-1］）x+a［n-2］）x+……+a［1］）x+a［0］。

求多項式的值時，首先計算最內層括號內一次多項式的值，即

v［1］=a［n］x+a［n-1］

然後由內向外逐層計算一次多項式的值，即

v［2］=v［1］x+a［n-2］

v［3］=旦禒測溉爻防詫獅超餞v［2］x+a［n-3］

……

v［n］=v［n-1］x+a［0］

這樣，求n次多項式f（x）的值就轉化為求n個一次多項式的值。

（注：中括號裡的數表示下標）

結論：對於一個n次多項式，至多做n次乘法和n次加法。

［編輯本段］意義

該演算法看似簡單，其最大的意義在於將求n次多項式的值轉化為求n個一次多項式的值。在人工計算時，利用秦九韶演算法和其中的係數表可以大幅簡化運算；對於計算機程式演算法而言，加法比乘法的計算效率要高很多，因此該演算法仍有極大的意義，用於減少cpu運算時間。