浅谈秦九韶算法
好像FFT要用到,所以就学习一下
听说还是高中必修三的内容?
文章目录
- 浅谈秦九韶算法
- 秦九韶算法的应用:
- code
秦九韶算法的应用:
当我们知道 x x x 的值时,求下列式子的值:
f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n − 1 x n − 1 + a n x n f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_{n - 1}x^{n - 1} + a_nx^n f(x)=a0+a1x+a2x2+a3x3+⋯+an−1xn−1+anxn
一开始看到这个式子,我们肯定会想到直接带 x x x 进去乘不就行了吗
那秦九韶还提出来干什么
我们发现单单一个 x n x^n xn 就需要 n − 1 n - 1 n−1 次乘法,那么一共就需要 ∑ i = 1 n − 1 i \sum_{i = 1} ^ {n - 1}i ∑i=1n−1i 次乘法,和 n n n 次加法,如下 n = 5 n = 5 n=5 时:
f ( x ) = a 0 + a 1 x + a 2 x + a 3 x + a 4 x + a 5 x f(x) = a_0 + a_1x + a_2x + a_3x + a_4x + a_5x f(x)=a0+a1x+a2x+a3x+a4x+a5x
就需要 10 10 10 次乘法和 5 5 5 次加法。
显然这个十分复杂,所以才要用到奏九韶算法
秦九韶算法就是将上述式子一步步化简成如下式子:
f ( x ) = ( ⋯ ( a n x + a n − 1 ) x + a n − 2 ) x + ⋯ + a 1 ) x + a 0 f(x) = ( \cdots (a_nx + a_{n - 1})x + a_{n - 2})x + \cdots + a_1)x + a_0 f(x)=(⋯(anx+an−1)x+an−2)x+⋯+a1)x+a0
我们发现这个虽然还是要用到 n n n 次加法,但是乘法次数下降到了 n − 1 n - 1 n−1 次,所以这个只需要 O ( n ) O(n) O(n)的时间就可以实现了。
code
代码十分短
void qinjiushao()
{for(int i=n-1;i>=1;i--)ans*=x,ans+=a[i];
}