Findet einen Algorithmus für das nächste Problem: Gegebene Menge S von n Punkten in der 2D-Ebene, ein Punkt (x1, y1) dominiert einen anderen Punkt (x2, y2), wenn x1 & gt; x2 und y1 & gt; y2. Finde die größte Menge von Punkten M, so dass M eine Teilmenge von S ist und kein Punkt von M von einem anderen Punkt von S dominiert wird.
Sortieren Sie alle Punkte, indem Sie x-Koordinaten erhöhen. Wenn zwei Punkte dieselbe x-Koordinate haben, sortieren Sie sie, indem Sie die y-Koordinaten verringern. Nun kann gezeigt werden, dass eine Teilmenge von Punkten genau dann nichtdominiert ist, wenn ihre y-Koordinaten in unserer sortierten Sequenz nicht ansteigend sind, was bedeutet, dass jede y-Koordinate kleiner oder gleich der vorherigen in der Teilsequenz ist. p>
Also wäre der Algorithmus:
Dies gibt die größtmögliche Menge in O (n * logn).
Es gibt einen Divide and Conquer-Algorithmus, der dies in O (n * logn) -Zeit macht.
Teilen wir die Punkte in zwei Hälften mit einer Größe von n / 2, basierend auf ihren x-Koordinaten. Wir finden den nicht dominierten Punkt in beiden Hälften. Sie müssen beachten, dass alle nicht dominierten Punkte in der rechten Hälfte in unserer endgültigen Liste vorhanden sind.
Mit dieser Beobachtung können wir unseren Kombinationsschritt schreiben, entfernen Sie alle nicht-dominierten Punkte in der linken Hälfte, deren y-Koordinate kleiner ist als die höchste y-Koordinate des Punktes in der nicht-dominierten Menge in der rechten Hälfte . Wir haben die Menge der nicht-dominierten Punkte.
Algorithmus:
%Vor%Gleichung für die Zeit:
%Vor%Sie können dies weiter zu O (n * logH) verbessern, wobei H die Anzahl der nicht dominierten Punkte ist, es erfordert mehr Einsicht in das Problem und es ist eine gute Erweiterung für Sie, um daran zu arbeiten.