Ich möchte die Existenz eines Algorithmus beweisen oder widerlegen, der bei einem Array von ganzen Zahlen drei Indizes und so dass und (oder stellt fest, dass es kein solches Tripel gibt) in linearer Zeit.i , j k i < j < k A [ i ] < A [ j ] < A [ k ]
Dies ist keine Hausaufgabe. Ich habe es in einem Programmierforum gesehen, in dem es heißt: "Versuche einen solchen Algorithmus zu implementieren." Ich vermute, dass es nach verschiedenen Experimenten unmöglich ist. Meine Intuition sagt es mir, aber das zählt nicht wirklich für irgendetwas.
Ich würde es gerne formal beweisen. Wie machst du das? Ich würde im Idealfall gerne einen Beweis sehen, der Schritt für Schritt erstellt wird, und wenn Sie dazu geneigt sind, eine Erklärung, wie einfache Fragen wie diese im Allgemeinen zu beweisen / zu widerlegen sind. Wenn es hilft, einige Beispiele:
[1,5,2,0,3] → (1,2,3)
[5,6,1,2,3] → (1,2,3)
[1,5,2,3] → (1,2,3)
[5,6,1,2,7] → (1,2,7)
[5,6,1,2,7,8] → (1,2,7)
[1,2,999,3] → (1,2,999)
[999,1,2,3] → (1,2,3)
[11,12,8,9,5,6,3,4,1,2,3] → (1,2,3)
[1,5,2,0,-5,-2,-1] → (-5,-2,-1)
Ich nahm an, dass man über iterieren könnte , und jedes Mal, wenn es ein (unser aktuelles , das heißt) gibt, machen wir ein neues Tripel und schieben es auf ein Array. Wir gehen weiter und vergleichen jedes Tripel, bis eines unserer Tripel vollständig ist. So ist es wie , ! Ich halte dies jedoch für komplexer als nur da die Anzahl der Tripel in unserem Triple-Array im schlimmsten Fall der Größe der Eingabeliste entsprechen würde.i < j j O ( n )[1,5,2,0,-5,-2,-1] → 1..2.. -5.. -2.. -1
[1,5,2,0,-5,-2,3,-1] → 1..2.. -5.. -2.. 3
quelle
Antworten:
Dies ist eine Variation des Problems mit der längsten zunehmenden Folge . Dies ist die auf Wikipedia vorgestellte Lösung, die zwei Hilfsarrays und P verwendet :M P
Dieser Algorithmus läuft im ungünstigsten Fall . Ihr Problem ist ein Sonderfall, der es Ihnen ermöglicht, zurückzukehren, wenn L = 3 ist, was die Laufzeit auf O ( n ) drückt, da die binäre Suche nur für Arrays mit einer Länge von höchstens zwei ausgeführt wird, was sich daher in der Zeit O ( 1 ) im Gegensatz zu befindet Θ ( log n ) im allgemeinen Fall.Θ ( n logn ) L = 3 O ( n ) O ( 1 ) Θ ( logn )
Betrachten Sie den modifizierten Pseudocode:
quelle
Ein Hinweis zur Methodik
Ich habe ein wenig über dieses Problem nachgedacht und bin zu einer Lösung gekommen. Als ich die Antwort von Saeed Amiri las , stellte ich fest, dass ich eine spezielle Version des Standardalgorithmus für die Suche nach der längsten Teilsequenz für eine Sequenz der Länge 3 gefunden hatte ist ein interessantes Beispiel für die Problemlösung.
Die Zwei-Elemente-Version
Dieser Fall ist sehr einfach; Wir werden versuchen, es zu verallgemeinern. Es zeigt sich, dass das angegebene Problem nicht lösbar ist: Die angeforderten Indizes existieren nicht immer. Wir werden daher eher darum bitten, dass der Algorithmus entweder gültige Indizes zurückgibt, wenn sie existieren, oder korrekt behauptet, dass keine solchen Indizes existieren.
Den Algorithmus finden
Wir haben gerade gesehen, dass die angeforderten Indizes nicht immer existieren. Unsere Strategie besteht darin, zu untersuchen, wann die Indizes nicht existieren. Wir werden dies tun, indem wir annehmen, dass wir versuchen, die Indizes zu finden und zu sehen, wie unsere Suche schief gehen könnte. Dann liefern die Fälle, in denen die Suche nicht schief geht, einen Algorithmus, um die Indizes zu finden.
Aussage des Algorithmus
In der Python-Syntax angegeben, aber beachten Sie, dass ich es nicht getestet habe.
Proof-Skizze
index1
ist der Index des Minimums des Teils des Arrays, der bereits durchlaufen wurde (wenn er mehrmals auftritt, wird das erste Vorkommen beibehalten) oderNone
bevor das erste Element verarbeitet wird.index2
speichert die Indizes der ansteigenden Teilsequenz der Länge 2 im bereits durchquerten Teil des Arrays, der das niedrigste größte Element hat, oderNone
wenn eine solche Sequenz nicht existiert.Wenn
return (index2[0], index2[1], i)
läuft, haben wirvalue2[0] < value[1]
(dies ist eine Invariante vonvalue2
) undvalue[1] < A[i]
(aus dem Kontext ersichtlich). Wenn die Schleife endet, ohne die frühe Rückkehr aufzurufenvalue1 == None
, gibt es in diesem Fall entweder keine zunehmende Teilfolge der Länge 2, geschweige denn der Länge 3, oder sievalue1
enthält die zunehmende Teilfolge der Länge 2, die das niedrigste größte Element aufweist. Im letzteren Fall haben wir weiterhin die Invariante, dass keine zunehmende Folge der Länge 3 früher endet alsvalue1
; daher würde das letzte Element einer solchen hinzugefügtenvalue2
Teilsequenz eine zunehmende Teilsequenz der Länge 3 bilden: da wir dort auch die Invariante haben,value2
die nicht Teil einer zunehmenden Teilsequenz der Länge 3 ist, die in dem bereits durchquerten Teil des Arrays enthalten ist ist keine solche Untersequenz im gesamten Array.Das Beweisen der vorgenannten Invarianten bleibt dem Leser als Übung überlassen.
Komplexität
Formeller Beweis
Dem Leser als Übung überlassen.
quelle
Durchlaufen Sie zunächst das Array von links nach rechts, und verwalten Sie dabei einen Stapel und ein Hilfsarray, das Ihnen für jedes Element den Index eines Elements angibt, das größer als dieses ist, sowie rechts davon.
Jedes Mal, wenn Sie ein neues Element im Array in Betracht ziehen, entfernen Sie es aus dem Stack, wenn dieses Element größer als das oberste Element des Stapels ist, und legen das Aux-Array-Element entsprechend dem obersten fest, unter dem sich der Index des neuen Elements befindet Berücksichtigung.
Entfernen Sie weitere Elemente aus dem Stapel und setzen Sie den entsprechenden Index, während das aktuelle Element größer ist. Sobald die Oberseite ein Element hat, das nicht kleiner ist (oder leer wird), schieben Sie das aktuelle Element auf den Stapel und fahren Sie mit dem nächsten Element des Arrays fort, wobei Sie den obigen Schritt wiederholen.
Machen Sie einen weiteren Durchgang (und ein anderes Aux-Array), aber gehen Sie von rechts nach links.
Der Pseudocode für den ersten Durchgang könnte folgendermaßen aussehen:
quelle