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

21

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.

James Wierzba
quelle
8
Es ist unklar, wie "das größte Element" definiert werden würde? Welches Element ist beispielsweise am größten, wenn ? Haben Sie andere Vergleichsregeln? A>B,B>C,C>A
fade2black
6
Ich kann mir nicht vorstellen, wie wir das größte Element in einer Menge auswählen würden, das nicht zumindest teilweise geordnet ist. Bitte beachten Sie die Definition des größten und des kleinsten Elements. Fehlende Transitivität schließt Teilbestellungen aus.
fade2black
3
@ fade2black Warum verbindest du mich mit einer anderen Definition von "der Größte"? Ich erkläre ausdrücklich die Definition des Größten für den Kontext dieser Frage. Größtes Mittel, das Element ist größer als jedes andere Element. Kein Element ist gleich. Das ist alles was dazu gehört. Ist das nicht klar?
James Wierzba
2
Ihr letztes Beispiel mit A, B, C, D wäre hilfreich, um Ihre Frage zu verstehen, ob Sie sie in Ihr OP aufgenommen haben.
fade2black
3
Ein Mitglied des C # -Compilerteams stellte dies als Interviewfrage. Dies ist relevant, da in C # der Überladungsauflösungsalgorithmus das eindeutig beste Element einer Menge auswählen muss , wenn eine "Betterness" -Relation vorliegt, die normalerweise, aber nicht unbedingt transitiv ist. (Oder geben Sie eine passende Antwort, wenn es kein so einzigartiges bestes Mitglied gibt. Verbindungen sind möglich.) Obwohl ich es geschafft habe, sie richtig zu beantworten, hätte ich nie gedacht, dass es eine besonders gute Interviewfrage ist, da sie auf einem "Aha" -Einblick beruht, um die zu erhalten linearer Algorithmus.
Eric Lippert

Antworten:

38

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.ein1

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).<einichjicheinich>einj

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 i<<#einicheinicheinich>?einjeinich>einj 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.#einich<n-1einich<einjo(n2)

Ariel
quelle
1
@JamesWierzba (ich denke) er bedeutet nur, dass ein "übersprungenes" Element eines ist, das nicht größer ist als Ihr aktuelles Maximum. Berücksichtigen Sie den Standardalgorithmus: Sie vergleichen jeden Wert in Ihrer Liste mit dem aktuellen Maximum. Sie haben gesagt, dass es in jeder Liste ein größtes Element gibt. Irgendwann werden Sie das mit Ihrem aktuellen Maximum vergleichen und da es größer ist, wird dieser Wert Ihr neues Maximum. Da dieser Wert größer als alles andere in der Liste ist, werden Sie nie ein Element finden, das größer ist, und Ihr größter Wert wird nicht ersetzt. Nach Ihren nVergleichen muss Ihr aktuelles
Lord Farquaad,
1
Aus Gründen der Übersichtlichkeit wird bei diesem Algorithmus keine Transitivität vorausgesetzt. Wenn Sie das kaum glauben können, befolgen Sie die Details des Korrektheitsnachweises (nehmen Sie zum Zwecke des Widerspruchs an, dass der zurückgegebene Wert nicht das Maximum ist, und verwenden Sie die Idee aus dem ersten Absatz).
Ariel
7
Dies beruht auf der Annahme 2 in der Frage: Es gibt immer ein Maximum im Array. Wäre dies nicht der Fall, maxkönnte nur das Maximum eines Subarrays sein. Trotzdem kann man auch ohne Annahme 2 ein vorläufiges Maximum finden und es dann auf dem gesamten Array mit einem zweiten Scan innerhalb der O (n) -Grenze überprüfen.
Chi
7
Diese Antwort setzt voraus, dass und B > A nicht gleichzeitig gelten können. Soweit ich sehen kann, ist dies in der Frage nicht ausgeschlossen. A>BB>A
Emil Jeřábek unterstützt Monica
4
@ oconnor0 Das folgt nicht. Nehmen Sie für ein konkretes Beispiel an, dass A> B, A> C, B> A und C> B ist. Dann ist A größer als jedes andere Element in der Menge (und ist das einzige Element mit dieser Eigenschaft), aber wenn die Elemente sind In der Reihenfolge A, B, C wird der Algorithmus C ausgeben.
Emil Jeřábek unterstützt Monica
24

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.

Ilmari Karonen
quelle
3
Tatsächlich überspringt das OP viele Details. Zum Beispiel wird nichts über die Reflexivität der Beziehung gesagt, und wenn sie nicht reflexiv ist, if x > m:ist sie undefiniert.
fade2black
4

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.

n1

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.

Danikov
quelle
1
" Azyklisch gerichteter Graph " ist das falsche Modell: Es sollte stattdessen " Turnier " sein. Zyklen sind erlaubt und es ist entscheidend, dass jede Kante in genau einer Richtung existiert.
Peter Taylor
@PeterTaylor, Sie haben vollkommen recht. Ich habe nur über die Gewinne nachgedacht, die zum "größten" Element führen. Die anderen Gewinne sind weniger relevant, werden aber möglicherweise auf dem Weg zur Entdeckung des Größten durchlaufen, damit Sie recht haben, dass sie es können. nicht rabattiert werden
Danikov
3

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

EIN,B,C,D

EIN>B,B>C,C>EIN
D>EIN,D>B,D>C


ich=1: max=EIN
ich=2: max=EINEIN>B
ich=3: max=CEIN<C
ich=4: max=DD>C

m>eina<mamm<aamam

fade2black
quelle
Ich denke nicht, dass das erste else ifbenötigt wird. Es kann nicht ausgelöst werden, wenn maxes sich um das Maximum handelt, und wenn das Maximum noch nicht angetroffen wurde, spielt es keine Rolle, wie hoch der Wert maxist.
rici
Ja, das ist der erste. Der andere ist der zweite :)
rici
Du meinst ifs ohne elses lassen? Es ist nur eine Gewohnheit: Mit elses vergleichen wir nicht einmal. :)
fade2black
1
Wäre es nicht einfacher, nur maxein Element der Liste zu initialisieren und innerhalb der Schleife zu tun if max and a[i] are comparable and max < a[i] then max = a[i](wobei der erste Teil der Bedingung weggelassen werden könnte, wenn angenommen wird, dass der Versuch, zwei unvergleichbare Elemente zu vergleichen, immer falsch ist)?
Ilmari Karonen
1
@badallen das op geht davon aus, dass es immer das größte element gibt. In Ihrem Beispiel gibt es kein größtes Element.
fade2black
2

A<BB<A

A1...AnAi<Aj

n2

Ai<Ajj

j0Ai<Aj0ijijAi<AjiijAij<Ajj0ij

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<Ann2n

Corinna
quelle
1

A > Bn

O(n)

Ratschenfreak
quelle