O (m + n) algoritmo para interpolación lineal
-
29-09-2020 - |
Pregunta
Problema
Dados los datos que consisten en $ n $ coordenadas $ \ izquierda ((x_1, y_1), (x_2, y_2) , \ ldots, (x_n, y_n) \ derecha) $ ordenados por su $ x $ -values, y $ m $ Puntos de consulta ordenados $ (q_1, q_2, \ ldots, q_m) $ , encuentre los valores linealmente interpolados de los puntos de consulta de acuerdo con el datos. Asumimos $ q_i \ in (\ min_j x_j, \ max_j x_j) $
Escuché que este problema podría resolverse en $ o (m + n) $ tiempo, pero solo puedo pensar en un $ O (m \ log n) $ algoritmo. Parece que no puedo encontrar este problema en particular en ninguno de los libros de texto del algoritmo.
Algoritmo linealitmico
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)
Esto nos da un tiempo de ejecución de $ o (m \ log n) $ , no me está claro cómo obtener esto a $ o (m + n) $ Como búsqueda de $ x_i $ debe hacerse para cada punto de consulta.
Solución
Solo necesita realizar una búsqueda binaria del primer elemento y luego iterira simultáneamente a través de los puntos de datos y puntos de consulta.
Pseudocódigo
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)