Algoritmo O(m+n) per l'interpolazione lineare
-
29-09-2020 - |
Domanda
Problema
Dati dati costituiti da $n$ coordinate $\sinistra((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\destra)$ ordinati per loro $x$-valori e $m$ punti di query ordinati $(q_1, q_2, \ldots, q_m)$, trovare i valori interpolati linearmente dei punti di query in base ai dati.Assumiamo $q_i \in (\min_j x_j, \max_j x_j)$
Ho sentito dire che questo problema potrebbe essere risolto $O(m+n)$ tempo ma riesco solo a pensare a un $O(m \log n)$ algoritmo.Non riesco a trovare questo particolare problema in nessuno dei libri di testo sugli algoritmi.
Algoritmo lineare
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)
Questo ci dà un tempo di esecuzione di $O(m \log n)$, non mi è chiaro come arrivare a questo $O(m + n)$ come la ricerca di $x_i$ deve essere fatto per ogni punto di query.
Soluzione
È sufficiente eseguire la ricerca binaria per il primo elemento e quindi scorrere simultaneamente i punti dati e i punti query.
Pseudocodice
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)