Maxima der Diagonalen in einer spalten- und zeilenweise sortierten Matrix

Lassen $\{a_i\}$ und $\{b_i\}$ nicht abnehmende Folgen nicht negativer Ganzzahlen sein.

Wie schnell kann man finden

Naiv dauert es Zeit, aber ich hoffe, dass Monotonie hier helfen kann.$O(n^2)$

Es ist leicht zu beobachten, dass ebenfalls nicht abnimmt. Wenn wir die Matrix in der , dann ist es eine Matrix, die sowohl in Zeilen- als auch in Spaltenrichtung sortiert ist, und wir suchen nach dem maximalen Element in jeder Diagonale.$\{c_i\}$$M$$M_{i,j} = a_i+b_j$

Wenn es sich jedoch um eine beliebige spalten- und zeilenweise sortierte Matrix handelt, erfordert dieses Problem -Zeit.$\Omega(n^2)$

Beweis: Lassen Sie alle Zahlen unterhalb der Hauptdiagonale . Die Elemente in der ten Diagonale sind Zufallszahlen aus . Das Lesen eines Eintrags liefert keine Informationen für einen anderen Eintrag.$\infty$$k$$(k,k+1)$

Bearbeiten: Dieses Problem ist viel schwieriger als ich erwartet hatte. Wir können dieses Problem als Faltungsproblem über das Semiring modellieren (nimm das Dual, suche nach min statt max) und es kann in gelöst werden Zeit nach einer Antwort von Ryan Williams auf mathoverflow . Es wird jedoch nicht die Information verwendet, dass die Sequenz nicht abnimmt.$(\min,+)$$O(\frac{n^2}{\log n})$

Gute Frage! "Distance Transforms of Sampled Functions" von Felzenszwalb und Huttenlocher zeigt, wie man dies in berechnet .$O(n \lg n)$

"Halsketten, Faltungen und X + Y", Von Bremner et al. zeigt einen -Algorithmus für dieses Problem im realen RAM und einen Algorithmus im ungleichmäßigen linearen Entscheidungsbaummodell.$O\left(\frac{n^2}{\frac{\lg^2 n}{(\lg \lg n)^3}}\right)$$O(n \sqrt{n})$