用于线性插值的O（M + N）算法

Question

问题

给定数据由 $ n $ coordinates $ \ left（（x_1，y_1），（x_2，y_2） ，\ ldots，（x_n，y_n）\右）$ 按其 $ x $ -values， $ M $ 排序查询点 $（q_1，q_2，\ ldots，q_m）$ ，根据所需查询点的线性插值值数据。我们假设 $ q_i \ in（\ min_j x_j，\ max_j x_j）$

我已经听到了这个问题可以在 $ o（m + n）$ 时间内解决这个问题，但只能想到 $ O（m \ log n）$ 算法。我似乎无法在任何算法教科书中找到这个特殊问题。

线性算法

interpolated = []
for q in qs:
    find x[i] such that x[i] <= q <= x[i+1] with binary search
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

.

这给了我们一个 $ o（m \ log n）$ 的运行时，它不清楚如何将此降至 $ O（m + n）$ 作为搜索 $ x_i $ 必须为每个查询点完成。

Answer 1

您只需要对第一个元素执行二进制搜索，然后通过数据点和查询点同时迭代。

伪码

interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search

for q in qs:
    while not x[i] <= q <= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

.