# Horner's Method

which also call as QinJiuSao's Method in China, because QinJiuSao pubulished the method in 1247 while Horner pubilshed in 1819.

Horner's Method is an algorithm for calculating polynomials in a computational efficient way.

$$p(x) = \sum_{i=0}^{n}a_i * x^{n-i}$$

Intuitively, it seams we need $\frac{n(n+1)}{2}$ times Multiplies and $n$ times Additons. But things chanegd if it is transformed to the follow expression.
$$p(x) = (...(a_0x+a_1)x + a_2)...+a_{n-1})x+a_n$$

Obviously, it is just a recursion defination of the previous polynomial which can be present as below.

$$
\begin{equation}
\left\{
             \begin{array}{lr}
             b_0=a_0, &  \\
             b_i = b_{i-1} * x^* + a_i, & i = 1,2,...,n  
             \end{array}
\right.
\end{equation}
$$

Evidently, it just takes $n$ times Multiplies and $n$ times Additions.

# 秦九韶算法

用于计算多项式，将原来的需要$n^2$的运算复杂度降低到了$n$。算法的迭代表达式如上公式。

b3638af68e3e04800e3f6358fe062e3372818993
ipynb
Jupyter Notebook
Numerical Analysis/Horner method/.ipynb_checkpoints/README-checkpoint.ipynb
Sean16SYSU/Algorithms4N
24f06c29d476c4bd9c90bcc89dac90ba3a448c27
MIT
2019-09-30T01:26:41.000Z
2019-10-02T01:36:34.000Z
Numerical Analysis/Horner method/.ipynb_checkpoints/README-checkpoint.ipynb
Sean16SYSU/Algorithms4N
24f06c29d476c4bd9c90bcc89dac90ba3a448c27
MIT
Numerical Analysis/Horner method/.ipynb_checkpoints/README-checkpoint.ipynb
Sean16SYSU/Algorithms4N
24f06c29d476c4bd9c90bcc89dac90ba3a448c27
MIT
2020-05-18T15:09:01.000Z
2020-12-21T10:14:51.000Z
Qwen/Qwen-72B
1. YES
2. YES