跳转至

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

## 多项式的多点求值

### 描述

给出一个多项式 𝑓(𝑥)f(x) 和 𝑛 n 个点 𝑥 1,𝑥 2,…,𝑥 𝑛 x 1,x 2,…,x n，求

𝑓(𝑥 1),𝑓(𝑥 2),…,𝑓(𝑥 𝑛)f(x 1),f(x 2),…,f(x n)

### 解法

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

将给定的点分为两部分：

𝑋 0={𝑥 1,𝑥 2,…,𝑥⌊𝑛 2⌋}𝑋 1={𝑥⌊𝑛 2⌋+1,𝑥⌊𝑛 2⌋+2,…,𝑥 𝑛}X 0={x 1,x 2,…,x⌊n 2⌋}X 1={x⌊n 2⌋+1,x⌊n 2⌋+2,…,x n}

构造多项式

𝑔 0(𝑥)=∏𝑥 𝑖∈𝑋 0(𝑥−𝑥 𝑖)g 0(x)=∏x i∈X 0(x−x i)

则有 ∀𝑥 ∈𝑋 0 :𝑔 0(𝑥) =0∀x∈X 0:g 0(x)=0．

考虑将 𝑓(𝑥)f(x) 表示为 𝑔 0(𝑥)𝑄(𝑥) +𝑓 0(𝑥)g 0(x)Q(x)+f 0(x) 的形式，即：

𝑓 0(𝑥)≡𝑓(𝑥)(m o d 𝑔 0(𝑥))f 0(x)≡f(x)(mod g 0(x))

则有 ∀𝑥 ∈𝑋 0 :𝑓(𝑥) =𝑔 0(𝑥)𝑄(𝑥) +𝑓 0(𝑥) =𝑓 0(𝑥)∀x∈X 0:f(x)=g 0(x)Q(x)+f 0(x)=f 0(x)，𝑋 1 X 1 同理．

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

时间复杂度

𝑇(𝑛)=2 𝑇(𝑛 2)+𝑂(𝑛 l o g⁡𝑛)=𝑂(𝑛 l o g 2⁡𝑛)T(n)=2 T(n 2)+O(n log⁡n)=O(n log 2⁡n)

## 多项式的快速插值

### 描述

给出一个 𝑛 +1 n+1 个点的集合

𝑋={(𝑥 0,𝑦 0),(𝑥 1,𝑦 1),…,(𝑥 𝑛,𝑦 𝑛)}X={(x 0,y 0),(x 1,y 1),…,(x n,y n)}

求一个 𝑛 n 次多项式 𝑓(𝑥)f(x) 使得其满足 ∀(𝑥,𝑦) ∈𝑋 :𝑓(𝑥) =𝑦∀(x,y)∈X:f(x)=y．

### 解法

考虑拉格朗日插值公式

𝑓(𝑥)=𝑛∑𝑖=1∏𝑗≠𝑖 𝑥−𝑥 𝑗 𝑥 𝑖−𝑥 𝑗 𝑦 𝑖 f(x)=∑i=1 n∏j≠i x−x j x i−x j y i

记多项式 𝑀(𝑥) =∏𝑛 𝑖=1(𝑥 −𝑥 𝑖)M(x)=∏i=1 n(x−x i)，由洛必达法则可知

∏𝑗≠𝑖(𝑥 𝑖−𝑥 𝑗)=l i m 𝑥→𝑥 𝑖∏𝑛 𝑗=1(𝑥−𝑥 𝑗)𝑥−𝑥 𝑖=𝑀′(𝑥 𝑖)∏j≠i(x i−x j)=lim x→x i∏j=1 n(x−x j)x−x i=M′(x i)

因此多项式被表示为

𝑓(𝑥)=𝑛∑𝑖=1 𝑦 𝑖 𝑀′(𝑥 𝑖)∏𝑗≠𝑖(𝑥−𝑥 𝑗)f(x)=∑i=1 n y i M′(x i)∏j≠i(x−x j)

我们首先通过分治计算出 𝑀(𝑥)M(x) 的系数表示，接着可以通过多点求值在 𝑂(𝑛 l o g 2⁡𝑛)O(n log 2⁡n) 时间内计算出所有的 𝑀′(𝑥 𝑖)M′(x i)．

我们令 𝑣 𝑖 =𝑦 𝑖 𝑀′(𝑥 𝑖)v i=y i M′(x i)，接下来考虑计算出 𝑓(𝑥)f(x)．对于 𝑛 =1 n=1 的情况，有 𝑓(𝑥) =𝑣 1,𝑀(𝑥) =𝑥 −𝑥 1 f(x)=v 1,M(x)=x−x 1．否则令

𝑓 0(𝑥)=⌊𝑛 2⌋∑𝑖=1 𝑣 𝑖∏𝑗≠𝑖∧𝑗≤⌊𝑛 2⌋(𝑥−𝑥 𝑗)𝑀 0(𝑥)=⌊𝑛 2⌋∏𝑖=1(𝑥−𝑥 𝑖)𝑓 1(𝑥)=𝑛∑𝑖=⌊𝑛 2⌋+1 𝑣 𝑖∏𝑗≠𝑖∧⌊𝑛 2⌋<𝑗≤𝑛(𝑥−𝑥 𝑗)𝑀 1(𝑥)=𝑛∏𝑖=⌊𝑛 2⌋+1(𝑥−𝑥 𝑖)f 0(x)=∑i=1⌊n 2⌋v i∏j≠i∧j≤⌊n 2⌋(x−x j)M 0(x)=∏i=1⌊n 2⌋(x−x i)f 1(x)=∑i=⌊n 2⌋+1 n v i∏j≠i∧⌊n 2⌋<j≤n(x−x j)M 1(x)=∏i=⌊n 2⌋+1 n(x−x i)

可得 𝑓(𝑥) =𝑓 0(𝑥)𝑀 1(𝑥) +𝑓 1(𝑥)𝑀 0(𝑥),𝑀(𝑥) =𝑀 0(𝑥)𝑀 1(𝑥)f(x)=f 0(x)M 1(x)+f 1(x)M 0(x),M(x)=M 0(x)M 1(x)，因此可以分治计算，这一部分的复杂度同样是 𝑂(𝑛 l o g 2⁡𝑛)O(n log 2⁡n)．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：fps5283, Tiphereth-A, TrisolarisHD, Enter-tainer, EntropyIncreaser, H-J-Granger, ImpleLee, Ir1d, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用