浅谈秦九韶算法焦点信息

2023-04-24 19:11:44 来源：博客园

(资料图片)

浅谈秦九韶算法

~~好像FFT要用到，所以就学习一下听说还是高中必修三的内容？~~

浅谈秦九韶算法
- 秦九韶算法的应用：
- code

秦九韶算法的应用：

当我们知道 \(x\) 的值时，求下列式子的值：

\[f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_{n - 1}x^{n - 1} + a_nx^n\]

一开始看到这个式子，我们肯定会想到直接带 \(x\) 进去乘不就行了吗~~那秦九韶还提出来干什么~~我们发现单单一个 \(x^n\) 就需要 \(n - 1\) 次乘法，那么一共就需要 \(\sum_{i = 1} ^ {n - 1}i\) 次乘法，和 \(n\) 次加法，如下 \(n = 5\) 时：

\[f(x) = a_0 + a_1x + a_2x + a_3x + a_4x + a_5x\]

就需要 \(10\) 次乘法和 \(5\) 次加法。~~显然这个十分复杂，所以才要用到奏九韶算法~~秦九韶算法就是将上述式子一步步化简成如下式子:

\[f(x) = ( \cdots (a_nx + a_{n - 1})x + a_{n - 2})x + \cdots + a_1)x + a_0\]

我们发现这个虽然还是要用到 \(n\) 次加法，但是乘法次数下降到了 \(n - 1\) 次，所以这个只需要 \(O(n)\)的时间就可以实现了。

code

代码十分短

void qinjiushao(){    for(int i=n-1;i>=1;i--)        ans*=x,ans+=a[i];}

关键词：