O (m + n) Algorithmus für lineare Interpolation

Question

Problem

Angegebene Daten, die aus $ N $ Koordinaten $ \ Left ((x_1, y_1), (x_2, y_2) , \ ldots, (x_n, y_n) \ Right) $ sortiert nach ihrer $ x $ -Values, und $ M $ sortierte Abfragepunkte $ (q_1, q_2, \ ldots, q_m) $ , Finden Sie die linear interpolierten Werte der Abfragepunkte nach dem Daten. Wir gehen davon aus, dass $ q_i \ in (\ min_j x_j, \ max_j x_j) $

Ich habe außerhalb der Hand gehört, dass dieses Problem in $ O (M + N) $ Time gelöst werden konnte, sondern kann nur an eine $ o (m \ log n) $ Algorithmus. Ich kann dieses spezielle Problem in keinem der Algorithmus-Lehrbücher finden.

linearithmischer Algorithmus

generasacodicetagpre.

Dies gibt uns eine Laufzeit von $ o (m \ log n) $ , es ist mir unklar, wie Sie dies auf $ o (m + n) $ Da die Suche nach $ x_i $ muss für jeden Abfragepunkt erfolgen.

Answer 1

Sie müssen nur eine binäre Suche nach dem ersten Element durchführen und gleichzeitig über die Datenpunkte und Abfragepunkte iterieren.

Pseudocode

generasacodicetagpre.