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

多项式的多点求值

描述

给出一个多项式 和 个点 ，求

解法

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

将给定的点分为两部分：

构造多项式

则有 。

考虑将 表示为 的形式，即：

则有 ， 同理。

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

时间复杂度

多项式的快速插值

描述

给出一个 个点的集合

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

解法

考虑拉格朗日插值公式

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

因此多项式被表示为

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

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

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