(资料图片仅供参考)

浅谈秦九韶算法

好像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];}