in O (n) Zeit: Finde das größte Element in der Menge, in der der Vergleich nicht transitiv ist

Titel gibt die Frage an.

Wir haben als Eingaben eine Liste von Elementen, die wir vergleichen können (bestimmen, welches das größte ist ). Kein Element kann gleich sein.

Wichtige Punkte:

1. Der Vergleich ist nicht transitiv (denken Sie an eine Steinpapierschere): Dies kann wahr sein: A> B, B> C, C> A (beachten Sie, dass dies keine gültige Eingabe ist, da es hier keine gültige Antwort gibt. nicht-transitiver Vergleich "bedeutet)
2. Jedes Eingabearray hat garantiert eine Antwort
3. Am größten bedeutet, dass das Element größer sein muss als jedes andere Element
4. Umgekehrte Eigenschaft gilt, dh A> B impliziert, dass B <A

Beispiel:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

Ich kann keinen Weg finden, dies in O (n) Zeit zu tun. Meine beste Lösung ist O (n ^ 2).

Ich bleibe bei jedem Ansatz hängen, da das Element explizit mit jedem anderen Element verglichen werden muss, um zu beweisen, dass es tatsächlich die Antwort ist (weil der Vergleich nicht transitiv ist).

Dies schließt die Verwendung eines Haufens, Sortieren usw. aus.

Der Standardalgorithmus zum Finden eines Maximums funktioniert immer noch. Beginnen Sie mit und gehen Sie die Elemente durch. Wenn Sie einen größeren Wert sehen, aktualisieren Sie das Maximum auf diesen Wert. Der Grund dafür ist, dass jedes übersprungene Element kleiner als mindestens ein Element ist und daher nicht das Maximum sein kann.$a_1$

Um es klar auszudrücken, meine ich mit dem "Standardalgorithmus" Folgendes:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

Der Vollständigkeit halber werde ich hier auf die in den Kommentaren angesprochenen Punkte eingehen. Die Einstellung in der obigen Diskussion wird ein Maximum in Bezug auf eine antisymmetrische Beziehung zu finden , wo ein i ein Maximum ist , wenn für alle j ≠ i haben wir einen i > ein j . Der obige Algorithmus funktioniert unter der Annahme, dass ein Maximum existiert. Wenn dies jedoch nicht bekannt ist, kann das Vorhandensein eines Maximums überprüft werden und in Ilmari Karonen antworten).$<$$a_i$$j\neq i$$a_i>a_j$

Wenn nicht unbedingt antisymmetrisch ist, schlägt der obige Algorithmus fehl (wie Emil in den Kommentaren erwähnt hat). Wenn < eine willkürliche Beziehung ist (dh wir lockern sowohl die Transitivität als auch die Antisymmetrie), ist es nicht schwer zu zeigen, dass das Finden eines Maximums in linearer Zeit nicht möglich ist. Es bezeichne # a i die Anzahl der Male eine i in einer Abfrage teilgenommen hat , wir eine kontradiktorische Beziehung in einer Art und Weise festlegen , dass das Maximum kann nicht ohne genügend Anfragen enthüllt werden. Angesichts der Abfrage ein i > ? a j , antworte a i > a j wenn # a $<$$<$$\#a_i$$a_i$$a_i >?a_j$$a_i>a_j$ undansonsten a i < a j . Wenn die Anzahl der Abfragen 0 ( n 2 ) ist , wurde noch kein Maximum festgestellt, und es kann eines der Elemente in der Menge festgelegt werden.$\# a_i < n-1$$a_i<a_j$$o(n^2)$

Wie Ariel bemerkt , ist der Standard-Maximum-Finding-Algorithmus wie folgt:

def find_maximum(a):
    m = a[0]
    for x in a:
        if x > m: m = x
    return m

wird in der Tat ohne Änderung funktionieren, solange:

• jedes Elementpaar kann verglichen werden, und
• Die Eingabe enthält garantiert ein maximales Element, dh ein Element, das paarweise größer ist als jedes andere Element in der Eingabe.

^{(Die obige erste Annahme kann tatsächlich gelockert werden, auch ohne dass der Algorithmus geändert werden muss, solange angenommen wird, dass das maximale Element mit jedem anderen Element vergleichbar ist und das x > yimmer falsch ist, wenn die Elemente xund yunvergleichbar sind.)}

Insbesondere Ihre Behauptung, dass:

[…] Um eine Antwort zu erhalten, muss das Element explizit mit jedem anderen Element verglichen werden (da der Vergleich nicht transitiv ist).

trifft unter den oben angegebenen Annahmen nicht zu. Um zu beweisen, dass der obige Algorithmus immer das maximale Element findet, genügt es zu beachten, dass:

1. da die Schleife über alle Eingabeelemente iteriert, wird bei einer gewissen Iteration xdas maximale Element sein;
2. da das maximale Element paarweise größer als jedes andere Element ist, folgt, dass am Ende dieser Iteration mdas maximale Element ist; und
3. Da kein anderes Element paarweise größer als das maximale Element sein kann, mändert sich dies bei den nachfolgenden Iterationen nicht.

Daher ist am Ende der Schleife mimmer das maximale Element, wenn die Eingabe eins enthält.

Ps. Wenn die Eingabe nicht unbedingt immer ein maximales Element enthält, muss die Antwort des Kandidaten für jedes andere Element getestet werden, um zu überprüfen, ob sie wirklich maximal ist. Wir können dies jedoch immer noch in O ( n ) Zeit tun, nachdem der oben beschriebene Maximum-Finding-Algorithmus ausgeführt wurde:

def find_maximum_if_any(a):
    # step 1: find the maximum, if one exists
    m = a[0]
    for x in a:
        if x > m: m = x

    # step 2: verify that the element we found is indeed maximal
    for x in a:
        if x > m: return None  # the input contains no maximal element
    return m  # yes, m is a maximal element

^{(Ich gehe hier davon aus, dass die Relation >irreflexiv ist, dh kein Element kann größer sein als sich selbst. Wenn dies nicht unbedingt der Fall ist, sollte der Vergleich x > min Schritt 2 durch ersetzt werden x ≠ m and x > m, wobei ≠Identitätsvergleich bedeutet. Oder wir könnten einfach die Optimierung anwenden Unten angegeben.)}

Um die Richtigkeit dieser Variation des Algorithmus zu beweisen, betrachten Sie die beiden möglichen Fälle:

• Wenn die Eingabe ein maximales Element enthält, wird es in Schritt 1 (wie oben gezeigt) gefunden und in Schritt 2 bestätigt.
• Wenn der Eingang ist nicht ein maximales Element enthalten, wird der Schritt 1 wird am Ende wie einige beliebiges Element Kommissionierung m. Es spielt keine Rolle, um welches Element es sich handelt, da es in jedem Fall nicht maximal sein wird, und daher erkennt Schritt 2 dies und kehrt zurück None.

Wenn wir den Index von min dem Eingabearray speichern a, könnten wir Schritt 2 tatsächlich optimieren, um nur die Elemente zu überprüfen, die zuvor meingegangen sind a, da alle späteren Elemente bereits mit mSchritt 1 verglichen wurden. Diese Optimierung ändert jedoch nicht die Komplexität der asymptotischen Zeit des Algorithmus, der immer noch O ( n ) ist.

$O(n)$

Wenn Sie Ihre Liste mit Vergleichselementen durchgehen, kann jedes Element, das einen Vergleich "verliert", sofort verworfen werden, da es, um das größte zu sein, größer als ALLE anderen Elemente sein muss, damit es durch den einzelnen Verlust disqualifiziert wird.

$n-1$

Diese Lösung wird durch eine Feinheit ermöglicht: "Kein Element kann gleich sein", kombiniert mit der Tatsache, dass es immer ein größtes Element geben wird. Wenn wir Gewinnbeziehungen als gerichteten Graphen abbilden, ist es klar, dass wir das größte Element erreichen können, indem wir einfach den Gewinnen folgen.

Ich gehe davon aus, dass die Beziehung für mindestens ein einzelnes Element antisymmetrisch ist (was die Existenz des größten Elements garantiert), ansonsten ist die Aufgabe unmöglich. Wenn alle Elemente in der endlichen Menge vergleichbar sind, funktioniert die übliche Findungsmaximalprozedur.

Wenn einige Elemente nicht vergleichbar sind, funktioniert das folgende Verfahren

max = nil
For i=1 to n
   if max is nil then
      max = a[i]
   if max and a[i] are not comparable then
      max = nil
   else if max < a[i] then
      max = a[i]
End

$A,B,C,D$

$i=1:$ $\max = A$
$i=2:$ $\max = A$$A > B$
$i=3:$ $\max = C$$A < C$
$i=4:$ $\max = D$$D > C$

$m>a$$a < m$$a$$m$$m<a$$a$$m$$a$$m$

$A<B$$B<A$

$A_1 ... A_n$$A_i<A_j$

$n^2$

$A_i<A_j$$j$

$j_0$$A_i < A_{j_0}\forall i$$j$$i_j$$A_i<A_j \forall i\neq i_j$$A_{i_j} < A_j$$j_0$$i_j$

Ich hoffe das ist etwas verständlich. Fühlen Sie sich frei, in Kommentaren zu fragen oder zu bearbeiten.

Die Grundidee ist, dass Sie keine Informationen über die verbleibenden Elemente von denjenigen sammeln können, die Sie bereits kennen, wenn Sie eine völlig willkürliche Beziehung zulassen.

$A<A$$n$$n^2-n$

A > B$n$

$O(n)$