您当前的位置： 首页 > 资讯 > 正文

世界速读：浅谈秦九韶算法

2023-04-24 23:22:21 来源：博客园 分享到：


(资料图片仅供参考)

浅谈秦九韶算法

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

关键词：

上一篇:库里4场季后赛砍126分 35岁后直追乔丹贾巴尔|全球速看 上一篇:最后一页

推荐阅读

更多阅读

关键词
x 广告
资讯 业界 企业
产品 服务 生活

休闲

Copyright   2015-2022 现在超市网版权所有  备案号：粤ICP备18023326号-5   联系邮箱：855 729 8@qq.com