o (m + n) 선형 보간을위한 알고리즘

Question

문제

$ n $ $ \ 왼쪽 ((x_1, y_1), (x_2, y_2)로 구성된 데이터가 주어집니다. , \ ldots, (x_n, y_n) \ 오른쪽) $ $ x $ - 값 및 $ 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)

.