Ich habe eine teilweise geordnete Menge, sagen wir A = [x1, x2, ...] , was bedeutet, dass für jede xi und xj in der Menge (genau) eine von vier Möglichkeiten zutrifft: xi < xj , xi == xj , xi > xj , oder xi und xj sind unvergleichbar.
Ich möchte die maximalen Elemente finden (d. h. jene Elemente xi , für die es keine Elemente xj mit xi < xj gibt). Was ist ein effizienter Algorithmus, um dies zu tun (die Anzahl der Vergleiche minimieren)? Ich habe versucht, eine DAG zu erstellen und eine topologische Sortierung durchzuführen, aber das Erstellen des Graphen erfordert O (n ^ 2) Vergleiche, was zu viele ist.
Ich mache das in Python, aber wenn Sie es nicht wissen, kann ich andere Sprachen oder Pseudocode lesen.
Es scheint, dass der schlimmste Fall O (n ^ 2) ist, egal was du tust. Zum Beispiel, wenn keine Elemente vergleichbar sind, dann müssen Sie jedes Element mit jedem anderen Element vergleichen, um zu bestimmen, dass sie alle maximal sind.
Und wenn Sie O (n ^ 2) erlauben, können Sie, da die Reihenfolge transitiv ist, nur einen Durchlauf durch die Menge machen und eine Liste aller Elemente behalten, die bisher maximal sind; Jedes neue Element klopft alle maximalen Elemente aus, die & lt; es und wird zu der maximalen Liste hinzugefügt, wenn es nicht & lt; jedes maximale Element.
Im schlimmsten Fall können Sie nicht schneller als O (n ^ 2) sein. In der Tat, um zu überprüfen, dass alle Elemente für die Pose maximal sind, in der kein Element vergleichbar ist, müssen Sie jedes Paar Elemente vergleichen. Im schlimmsten Fall ist es also eindeutig quadratisch.
Angenommen, Sie haben sich alle (n wähle 2) Vergleiche angesehen, mit Ausnahme von einem, zwischen x i und x j , i! = j. In einigen Szenarien sind die einzigen zwei Kandidaten für das Maximum genau diese zwei, x und x
Wenn Sie x i und x j nicht vergleichen, können Sie nicht definitiv sagen, ob sie beide maximal sind oder ob nur einer von ihnen ist.
Daher müssen Sie alle möglichen (n wähle 2) (O (n 2 )) Vergleiche überprüfen.
Beachten Sie, dass Ihre teilweise geordnete Menge mit einer schwarzen Box angegeben wird, die einen Vergleich durchführt. Wenn die partiell geordnete Menge zu Beginn mit einer Grafik versehen ist, können Sie anschließend die Menge der maximalen Elemente in der Zeit unterhalb von O (n 2 ) finden.
Wie andere Antworten gezeigt haben, ist die Worst-Case-Komplexität O (n ^ 2).
Es gibt jedoch Heuristiken, die in der Praxis viel helfen können. Zum Beispiel, wenn die Menge A eine Teilmenge von Z ^ 2 (Integer-Paare) ist, dann können wir viele Punkte im Voraus eliminieren durch:
Dies ist von Kosten O (n). Es ist leicht zu sehen, dass jeder maximale Punkt in xy-Maximalen vorhanden ist. Es kann jedoch nicht maximale Punkte enthalten. Betrachten Sie zum Beispiel die Menge {(1,0), (0,1), (2,2)}.
Je nach Situation kann dies eine Heuristik sein, die gut genug ist. Sie können dies mit dem erschöpfenden Algorithmus auf der kleineren Menge xy-maximals verfolgen.
Allgemeiner wird dieses Problem als "Pareto Frontier" Berechnungsproblem bezeichnet. Hier sind gute Referenzen:
Insbesondere der BEST-Algorithmus aus der ersten Referenz ist sehr nützlich.