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


多项式的多点求值

描述

给出一个多项式 个点 ,求

解法

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

将给定的点分为两部分:

构造多项式

则有

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

则有 同理。

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

时间复杂度

多项式的快速插值

描述

给出一个 个点的集合

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

解法

考虑拉格朗日插值公式

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

因此多项式被表示为

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

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

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

贡献者:@Imple@mgt@H-J-Granger@EntropyIncreaser@Ir1d@TrisolarisHD

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

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