拉格朗日插值公式看起来很复杂，其实自己举一个例子解一解就很容易明白了。读书的过程中发现，越是归结为简单形式的式子，用计算机编程实现起来越容易，优化的地方也就越多；举完例子发现，这玩意如果式子长了的话，还真不是人解的……
跟我们的目标接近一下（我们的目标是求C(x)，且C(x)=A(x)*B(x)），那么对A,B的任意一点(xk,yk)，都有C(xk)=A(xk)*B(xk)。
所以，想求两个多项式的乘积的时候，除了直接用系数表达来求，还可以用点值表达来求：
先求出A(x)、B(x)的点值表达，再相乘。这个过程需要O(n)。再将点值表达插值转成系数表达需要O(n^2)。
乍一看和前面描述的直接用系数表达求得结果的复杂度一样，都是O(n^2)的。实际上，点值表达中取点可以影响计算。用FFT可以将复杂度降到O(nlgn)。
拉格朗日插值公式以及一些变形 拉格朗日插值公式看起来很复杂，其实自己举一个例子解一解就很容易明白了。读书的过程中发...
多项式与快速傅立叶变换 按捺不住，终于还是想把FFT学一遍。在青岛站的热身赛看到一道题的数据范围特别大，顿时不知所...
这部分是关于ＤＦＴ和ＩＤＦＴ的。首先是单位复数根的定义，根据欧拉公式，将θ拆分为n份，那么每一个分割点在极坐标系下...
date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....
date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....
注：学习算法导论，按照标准伪代码理解翻译为java实现，如有兴趣理解整个过程的细节，建议阅读《算法导论》第7章：快...
算法导论 算法导论是一本书，1000多页，决定好好吸收下，毕竟算法非常重要。至于纸质书还是电子版，随意 公开课 2...
模块二 领导团队 第16讲 模块导论: 为什么组织要先搭班子？ ➖➖➖➖➖➖➖➖➖➖➖➖➖➖➖ ️模块导论: 为什...
这是算法导论里面的算法，排序算法是稳定的。 思考： 为什么9~11的for循环里要倒着遍历？这样倒着遍历，而且放进...
数据结构 数据结构与算法分析_Java语言描述(第2版) 算法 计算机算法基础算法导论编程之法_面试和算法心得 c...
本文标题：《算法导论》读书笔记 kirai 16/11/18 第30章 多
本文链接：https://www.haomeiwen.com/subject/lavjpttx.html
网友评论