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

多项式的多点求值

描述

给出一个多项式 个点 ,求

解法

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

将给定的点分为两部分:

构造多项式

则有

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

则有 同理。

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

时间复杂度

多项式的快速插值

描述

给出一个 个点的集合

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

解法

考虑拉格朗日插值公式

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

因此多项式被表示为

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

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

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