请你用写一段n次拉格朗日插值多项式的算法

以下是n次拉格朗日插值多项式的算法：

输入：n个数据点（x1,y1），（x2，y2），…，（xn，yn），要求在某个x值处进行插值。

输出：插值多项式P(x)

步骤1：定义n个拉格朗日插值基函数li(x)：

li(x) = Π(j ≠ i) (x - xj) / (xi - xj)

其中Π表示连乘积，i表示当前基函数的编号，xi和xj分别表示第i和第j个数据点的x值。

步骤2：定义插值多项式P(x)：

P(x) = Σ(i=1 -> n) yi * li(x)

其中Σ表示连加和，i表示当前数据点的编号，yi表示第i个数据点的y值，li(x)表示第i个拉格朗日插值基函数。

步骤3：返回插值多项式P(x)。

注：这个算法的时间复杂度为O(n^2)，因为每次计算插值多项式都需要计算n个拉格朗日插值基函数。如果需要多次使用插值多项式，可以将基函数提前计算出来，从而减少计算量。