O(m+n) de l'Algorithme d'Interpolation Linéaire

Question

Problème

De données composé de $n$ coordonnées $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) ight)$ triés en fonction de leur $x$-les valeurs, et $m$ requête triée points $(q_1, q_2, \ldots, q_m)$, trouver le interpolée linéairement les valeurs de la requête des points en fonction des données.Nous supposons $q_i \in (\min_j x_j, \max_j x_j)$

J'ai entendu de la main gauche que ce problème pourrait être résolu en $O(m+n)$ temps, mais ne peut que penser à un $O(m \log n)$ l'algorithme.Je n'arrive pas à trouver ce problème de l'algorithme de manuels scolaires.

Linearithmic Algorithme

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)

Cela nous donne un temps d'exécution de $O(m \log n)$, il est clair pour moi comment obtenez ce vers le bas pour $O(m + n)$ comme la recherche de $x_i$ doit être fait pour chaque point de requête.

Answer 1

Vous avez seulement besoin d'effectuer une recherche binaire pour le premier élément, puis itérer simultanément à travers les points de données de requête et de points.

Pseudocode

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)