Suche nach den dominierenden Paaren in einer Koordinatenmenge in O(nlgn)

Question

A Koordinate a(xa,ya) dominiert b(xb,yb) wenn ( xa>=xb und ya>=yb) Wie kann ich alle Paare in einem Koordinatensatz in nlgn mit divide et conquer finden?

edit:die Anzahl der Paare stattdessen.

Answer 1

Führen Sie eine Schnellsortierung durch, bei der Sie zuerst nach X und dann nach Y sortieren (Sie erhalten also etwa 5,3 5,2 4,7 4,2 usw.). Quicksort ist nlogn

Iterieren Sie dann einfach vom höchsten Punkt abwärts und vergleichen Sie. Das wäre höchstens O(n). Das Ergebnis ist O(n) + O(nlogn) => O(nlogn)

Quicksort arbeitet mit Teilen und Erobern - es teilt am Drehpunkt.

EDITAR:

Eine andere Sache, die ich in Betracht gezogen habe. Sie können die gesamte Menge ablaufen und alle Punkte, die in der X-Koordinate von Ihrem Punkt dominiert werden, in einer Menge zusammenfassen. Dann durchlaufen Sie diese kleinere Teilmenge und filtern diejenigen heraus, die auch von Ihrem Y dominiert werden. Das sind nur zwei Durchläufe, bei einer Leistung von O(n).

Answer 2

Grob gesagt dominiert jeder beliebige Vektor (xa,ya) etwa die Hälfte der anderen Vektoren (ya,yb) oder wird von ihnen dominiert, denn von den vier Fällen für {xa <=> ya, xb <=>yb} sind zwei Fälle von Dominanz.

Wir erwarten also, dass die Lösung Ihres Problems etwa n*(n/2) Paare von Vektoren umfasst. Der Algorithmus kann nicht billiger sein als seine Lösung, also wird n*ln(n) nicht funktionieren.

Answer 3

Nehmen wir an, Sie haben die Punkte so, dass

a1 > a2 > a3 ... > an-1 > an d (gelesen > als dominiert) n ist in allen Situationen proportional zur Anzahl der Punkte (N).

die Anzahl der Paare selbst ist größer als nlogn (z. B. (A[1],A[2..n]) (A2], A[3..n]) ..A[n=1], A[n]) Ich denke, das ist n (n-1) / 2.

N logN scheint also nicht möglich zu sein

Answer 4

Angenommen, Sie müssen nur zählen die Anzahl der Paare, können Sie den pauschalen Ansatz wählen:

1) Sortiere die Punkte nach ihren X-Werten

2) Sammeln Sie die Punkte in einem Suchbaum.

Hier verwenden wir einen ausgewogenen Baum, der auf den Y-Werten der Punkte basiert. Der Baum sollte für jeden internen Knoten einen Zähler haben, der die Anzahl der Elemente in dem von ihm verwurzelten Teilbaum angibt. Diese Zähler können ohne Auswirkungen auf die Zeitkomplexität der Baumoperationen gepflegt werden. Die Verwendung von Zählern ermöglicht die Abfrage der Anzahl von Elementen, die kleiner als ein bestimmter Wert V sind, in logarithmischer Zeit.

Weitere Einzelheiten zu (2): Wir scannen die in Schritt (1) erhaltenen Punkte von links nach rechts. Für jeden durchlaufenen Punkt P fügen wir P zum Baum hinzu und berechnen dann die Anzahl der Elemente mit Y < P.Y. Diese Anzahl wird zur globalen Anzahl hinzugefügt, die am Ende zurückgegeben wird.

Schritt (1) läuft in N*Log(N)-Zeit ab, und Schritt (2) führt N Iterationen von zwei Log(N)-Operationen durch, hat also die gleiche Komplexität.