拉格朗日插值学习笔记

拉格朗日插值定义给定一个多项式函数过点 \((x_i,y_i)\)，求出这个多项式函数的在 \(x=k\) 时的取值。公式 \[f(k)=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-x_j}{x_i-x_j} \]时间复杂度 \(O(n^2)\) 横坐标连续的