浅谈秦九韶算法
好像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)\)的时间就可以实现了。文章来源：https://www.toymoban.com/news/detail-423797.html
code
代码十分短文章来源地址https://www.toymoban.com/news/detail-423797.html
void qinjiushao()
{
for(int i=n-1;i>=1;i--)
ans*=x,ans+=a[i];
}
到了这里，关于浅谈秦九韶算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[控制原理基础]浅谈PID算法](https://imgs.yssmx.com/Uploads/2024/02/498192-1.png)
