多项式多点求值 |
您所在的位置:网站首页 › tan15度求值 › 多项式多点求值 |
多项式多点求值|快速插值多项式的多点求值描述 给出一个多项式 和 个点 ,求 解法考虑使用分治来将问题规模减半。 将给定的点分为两部分: 构造多项式 则有 。 考虑将 表示为 的形式,即: 则有 , 同理。 至此,问题的规模被减半,可以使用分治 + 多项式取模解决。 时间复杂度 多项式的快速插值描述给出一个 个点的集合 求一个 次多项式 使得其满足 。 解法考虑拉格朗日插值公式 记多项式 ,由洛必达法则可知 因此多项式被表示为 我们首先通过分治计算出 的系数表示,接着可以通过多点求值在 时间内计算出所有的 。 我们令 ,接下来考虑计算出 。对于 的情况,有 。否则令 可得 ,因此可以分治计算,这一部分的复杂度同样是 。 本页面最近更新:2022/12/20 15:31:23,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:Enter-tainer, EntropyIncreaser, fps5283, H-J-Granger, ImpleLee, Ir1d, TrisolarisHD本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |