用于线性插值的O(M + N)算法
-
29-09-2020 - |
题
问题
给定数据由 $ 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 $ 必须为每个查询点完成。
解决方案
您只需要对第一个元素执行二进制搜索,然后通过数据点和查询点同时迭代。
伪码
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)
. 不隶属于 cs.stackexchange