多项式多点求值 | 快速插值

本页面最后更新于: 2020/09/25


多项式的多点求值

Description

给出一个多项式 个点 ,求

Method

考虑使用分治来将问题规模减半。

将给定的点分为两部分:

构造多项式

则有

考虑将 表示为 的形式,即:

则有 同理。

至此,问题的规模被减半,可以使用分治 + 多项式取模解决。

时间复杂度

多项式的快速插值

Description

给出一个 个点的集合

求一个 次多项式 使得其满足

Method

考虑拉格朗日插值公式

记多项式 ,由洛必达法则可知

因此多项式被表示为

我们首先通过分治计算出 的系数表示,接着可以通过多点求值在 时间内计算出所有的

我们令 ,接下来考虑计算出 。对于 的情况,有 。否则令

可得 ,因此可以分治计算,这一部分的复杂度同样是

本页面最近更新:2020/09/25更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 SATA 协议之条款下提供,附加条款亦可能应用
0 条评论
未登录用户


Copyright © 2016 - 2020 OI Wiki Team

最近更新: c4f7a45, 2020-09-25

联系方式:Telegram 群组 / QQ 群组