拉格朗日插值可以在 $O(n^2)$ 的时间之内求解求解一个 $n$ 次多项式的表达式。

朴素的拉格朗日插值

现在要求解 $n$ 次函数 $f(x)$，已知 $f(x)$ 要过 $(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})$。

那么考虑构造 $n+1$ 可函数 $f_i(x)$ 满足：

$\left\{\begin{matrix} y_i & x=x_i\\ 0 & \text{Other wise.} \end{matrix}\right.$

那么显然就有：

$f(x)=\sum\limits_{i=1}^{n+1} f_i(x)$

容易发现通过以下方式构造的 $f_i(x)$ 满足要求：

$f_i(x)=y_i\times \prod\limits_{j=1\wedge j\ne i}^{n+1}\frac{x-x_j}{x_i-x_j}$

所以最后就得到了：

$f(x)=\sum\limits_{i=1}^{n+1} (y_i\times \prod\limits_{i=1}^{n+1} \frac{x-x_j}{x_i-x_j})$

横坐标是连续整数的拉格朗日插值

对于 $\forall i\in[1,n+1]\cap\mathbb{Z}\mid x_i=i$ 的情况，将其带入上式得到：

$f(x)=\sum\limits_{i=1}^{n+1}(y_i\times \prod\limits_{i=1\wedge i\ne j}^{n+1}\frac{x-j}{i-j})$

然后经过一些神奇的化简得到：

$f(x)=\sum\limits_{i=1}^{n+1}(-1)^{n+1-i}\times y_i\times \frac{\prod\limits_{i=1}^{n+1}(x-j)}{(i-1)!\times (n+1-i)!\times (x-i)}$