o (m + n) 선형 보간을위한 알고리즘
-
29-09-2020 - |
문제
문제
$ 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 $ 에 대한 검색이 모든 쿼리 지점에 대해 수행되어야합니다.
해결책
첫 번째 요소에 대한 이진 검색을 수행 한 다음 데이터 포인트와 쿼리 포인트를 통해 동시에 반복해야합니다.
의사
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