線形補間のためのO（M + N）アルゴリズム

Question

問題

$ n $ からなるデータが与えられた $ \ left（（x_1、y_1）、（x_2、y_2） 、\ ldots、（x_n、y_n）\ right）$ $ 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)

.