Gibt es einen Algorithmus mit dem man sortiert untersequenzen der Größe drei in $O(n)$ time?

Question

Ich will beweisen oder widerlegen Sie die Existenz eines Algorithmus, der, gegeben ein array $A$ der ganzen zahlen, findet drei Indizes $i, j$ und $k$, so dass $i < j < k$ und $A[i] < A[j] < A[k]$ (oder findet, dass es keine solche Dreibettzimmer), in der linearen Zeit.

Dies ist keine Hausaufgaben Frage;Ich sah es auf einer Programmierung forum gerahmt als "Versuch für die Umsetzung einer solchen Algorithmus." Ich vermute, dass es unmöglich ist, nach verschiedenen Experimenten.Meine intuition sagt mir, dass dem so ist, aber nicht wirklich zählen, für alles.

Ich möchte beweisen, dass es formal.Wie tun Sie es?Ich würde im Idealfall gerne sehen, ein Beweis legte Sie Schritt-durch-Schritt, und dann, wenn Sie so geneigt sind, eine Erklärung, wie man zu beweisen,/disproving einfache Fragen wie diese im Allgemeinen.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 die Iteration über $A$, und jedes mal, wenn es ein $i < j$ (unsere aktuelle " $j$, das ist), wir machen eine neue dreifach und schieben Sie es auf ein array.Wir sind weiterhin treten und der Vergleich der einzelnen triple, bis einer von uns triples abgeschlossen ist.Es ist also wie [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!Aber ich denke, das ist komplexer als bloße $\mathcal{O}(n)$ als die Anzahl der Tripel auf unsere triple-array würde im schlimmsten Fall entsprechen die Größe der input-Liste.

Answer 1

Dies ist die variation von Längste zunehmende Teilfolge problem;dies ist die Lösung präsentiert, die auf Wikipedia über zwei aux-arrays $M$ und $P$:

• $M[j]$ — speichert die position $k$ der kleinste Wert $A[k]$, so dass es eine steigende Teilfolge der Länge $j$ endet mit $A[k]$, die auf die Bereich $k \leq i$ (Hinweis: wir haben $j \leq k \leq i$, weil $j$ repräsentiert die Länge der zunehmende Teilfolge, und $k$ entspricht der position von - Beendigung.Offensichtlich, wir können nie einen zunehmenden Teilfolge der Länge $13$ endet an position $11$.$k \leq i$ durch definition).

• $P[k]$ — speichert die position des Vorgängers von $A[k]$ in der längsten zunehmende Teilfolge ending in $A[k]$.

  Neben der Algorithmus speichert eine variable $L$ repräsentiert die Länge der längste zunehmende Teilfolge gefunden so weit.

Dieser Algorithmus läuft in worst-case Zeit $ heta(n\log n)$.Ihr problem ist ein Sonderfall, können Sie Sie zurück, wenn $L=3$ die schiebt Laufzeit bis zu $O(n)$, da die binäre Suche kann nur auf arrays der Länge höchstens zwei, die deshalb in der Zeit $O(1)$ im Gegensatz zu $ heta(\log n)$ im Allgemeinen Fall.

Betrachten Sie die modifizierten pseudo-code:

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
   if L==3 : return true; // you can break here, and return true.
return false; // because L is smaller than 3.

Answer 2

Ein Hinweis zur Methodik

Ich dachte ein bisschen über dieses Problem nach und kam zu einer Lösung. Wenn ich lese Saeed Amiris Antwort, Ich erkannte, dass das, was ich mir ausgedacht habe Lösung.

Die Zwei-Elemente-Version

Fangen wir klein an: Anstatt nach drei Indizes zu suchen, bei denen die Elemente in Ordnung sind, suchen wir nach zwei: $ i <j $, so dass $ a [i] <a [j] $.

Wenn $ a $ abnimmt (dh $ forall i <j, a [i] ge a [j] $ oder gleichwertig $ forall i, a [i] ge a [i+1] $), dann Es gibt keine solchen Indizes. Ansonsten gibt es einen Index $ i $ so, dass $ a [i] <a [i+1] $.

Dieser Fall ist sehr einfach; Wir werden versuchen, es zu verallgemeinern. Es zeigt, dass das angegebene Problem nicht lösbar ist: Die angeforderten Indizes existieren nicht immer. Wir werden also eher darum bitten, dass der Algorithmus entweder gültige Indizes zurückgibt, wenn sie existieren, oder behauptet, dass keine solchen Indizes existieren.

Den Algorithmus aufnehmen

Ich werde den Begriff verwenden Subsequenz um einen Auszug aus dem Array $ a $ zu bedeuten, der aus Indizes besteht, die möglicherweise nicht aufeinanderfolgend sind ($ (a [i_1], ldots, a [i_m]) $ mit $ i_1 < dots <i_m $) und Lauf um aufeinanderfolgende Elemente von $ a $ ($ (a [i], a [i+1], ldots, a [i+m-1]) $) zu bedeuten.

Wir haben nur gesehen, dass die angeforderten Indizes nicht immer existieren. Unsere Strategie muss bestimmen, wenn 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 geht. Die Fälle, in denen die Suche nicht schief geht, liefert einen Algorithmus, um die Indizes zu finden.

Mit zwei Indizes konnten wir aufeinanderfolgende Indizes finden. Mit drei Indizes können wir möglicherweise nicht $ j = i+1 $ und $ k = j+1 $ entwickeln. Wir können jedoch den Fall berücksichtigen, wenn ein Lauf von drei streng wachsenden Elementen ($ a [i] <a [i+1] <a [i+2] $) zu gelöst wird, da es leicht zu erkennen ist, solche zu erkennen Läuft und sehen Sie, wie dieser Zustand möglicherweise nicht erfüllt wird. Angenommen, die Sequenz hat keinen streng zunehmenden Lauf von Länge 3.

Die Sequenz hat nur streng zunehmende Läufe von Länge 2 (die ich nennen werde bestellte Paare kurz), getrennt durch eine abnehmende Länge von mindestens 2. Damit ein streng zunehmender Lauf $ a [j] <a [j+1] $ Teil einer zunehmenden 3-Elemente-Sequenz ist, muss es eine geben Früheres Element $ i $ so, dass $ a [i] <a [j] $ oder ein späteres Element $ k $ so $ a [j+1] <a [k] $.

Ein Fall, in dem weder $ i $ noch $ k $ existiert, ist, wenn jedes bestellte Paar völlig niedriger ist als das nächste. Dies ist nicht alles: Wenn die Paare miteinander verbunden sind, müssen wir sie fein vergleichen.

Das linke Element $ i $ einer zunehmenden Subsequenz muss früh kommen und klein sein. Das nächste Element $ J $ muss größer sein, aber so klein wie möglich, um ein drittes größeres Element $ k $ zu finden. Das erste Element $ i $ ist nicht immer das kleinste Element in der Sequenz, und es ist nicht immer das erste, für das es ein nachfolgendes größeres Element gibt Eine bessere Passform für das bereits gefundene Minimum.

Wenn wir von links nach rechts gehen, wählen wir vorläufig das kleinste Element als $ i $. Wenn wir ein größeres Element weiter rechts finden, wählen wir dieses Paar als vorläufige $ (i, j) $ aus. Wenn wir noch größer sind, haben wir gewonnen. Das Wichtigste ist, dass unsere Wahl von $ i $ und unsere Auswahl von $ (i, j) $ unabhängig aktualisiert werden: Wenn wir einen Kandidaten $ (i, j) $ haben und wir $ I '> J $ so finden Das $ a [i '] <a [i] $, $ i' $ wird zum nächsten Kandidaten $ i $, aber $ (i, j) $ bleibt. Nur wenn wir $ j '$ so finden, dass $ a [j'] <a [j] $ $ $ (i ', j') $ wird zum neuen Kandidatenpaar.

Aussage des Algorithmus

Gegeben in der Python -Syntax, aber vorsicht, dass ich es nicht getestet habe.

def subsequence3(A):
    """Return the indices of a subsequence of length 3, or None if there is none."""
    index1 = None; value1 = None
    index2 = None; value2 = None
    for i in range(0,len(A)):
        if index1 == None or A[i] < value1:
            index1 = i; value1 = A[i]
        else if A[i] == value1: pass
        else if index2 == None:
            index2 = (index1, i); value2 = (value1, A[i])
        else if A[i] < value2[1]:
            index2[1] = i; value2[1] = A[i]
        else if A[i] > value2[1]:
            return (index2[0], index2[1], i)
    return None

Proof -Skizze

index1 ist der Index des Minimums des Teils des Arrays, der bereits durchquert wurde (wenn es mehrmals auftritt, behalten wir das erste Ereignis) oder oder None Vor der Verarbeitung des ersten Elements. index2 speichert die Indizes der zunehmenden Subsequenz von Länge 2 im bereits übertragenen Teil des Arrays, das das niedrigste größte Element aufweist, oder None Wenn eine solche Sequenz nicht existiert.

Wann return (index2[0], index2[1], i) Läufe, wir haben value2[0] < value[1] (Dies ist eine Invariante von value2) und value[1] < A[i] (offensichtlich aus dem Kontext). Wenn die Schleife endet, ohne die frühe Rückkehr zu berufen value1 == None, In diesem Fall gibt es keine zunehmende Untersequenz von Länge 2, geschweige denn 3 oder value1 Enthält die zunehmende Abfolge von Länge 2, die das niedrigste größte Element aufweist. Im letzteren Fall haben wir außerdem die Invariante, dass keine zunehmende Subquenz von Länge 3 früher als früher endet als value1; daher das letzte Element einer solchen Subsequenz, hinzugefügt zu value2, würde eine zunehmende Abfolge der Länge 3 bilden: Da wir auch die Invariante haben value2 ist nicht Teil einer zunehmenden Subsequenz von Länge 3, die im bereits übertragenen Teil des Arrays enthalten ist, es gibt keine solche Subsequenz im gesamten Array.

Das Beweisen der oben genannten Invarianten bleibt als Übung für den Leser.

Komplexität

Wir verwenden $ O (1) $ zusätzlicher Speicher und durchqueren das Array als Stream von links nach rechts. Wir führen für jedes Element $ o (1) $ verarbeitung durch, was zu einer Laufzeit von $ O (n) $ führt.

Formeller Beweis

Als Übung zum Leser gelassen.

Answer 3

Es gibt einen $ o (n) $ Time -Algorithmus, der $ O (n) $ Space verwendet.

Erstern Sie das Array von links nach rechts, wobei Sie einen Stapel und ein Hilfsarray erhalten, das Ihnen für jedes Element, den Index eines Elements, das größer als es und rechts ist, mitteilt.

Zunächst ist der Stapel leer und das Aux-Array enthält alle $ -1 $ s.

Jedes Mal, wenn Sie ein neues Element im Array betrachten. Wenn dieses Element größer ist als das obere Element des Stapels Rücksichtnahme.

Packen Sie die Elemente weiter aus dem Stapel und setzen Sie den entsprechenden Index fest, während das aktuelle Element größer ist. Sobald das Oberteil ein Element hat, das nicht geringer ist (oder leer wird), drücken Sie das aktuelle Element auf den Stapel und fahren Sie mit dem nächsten Element des Arrays fort, um den obigen Schritt zu wiederholen.

Machen Sie einen weiteren Pass (und ein weiteres Aux -Array), gehen Sie aber nach links.

Machen Sie einen Durchgang durch die Aux-Arrays und wählen Sie eine Position, bei der beide entsprechenden Einträge im Array nicht $ -1 $ sind.

Da Sie jedes Element des Arrays nur eine ständige Anzahl von Male betrachten, ist dies $ o (n) $ Zeit.

Ich glaube, Sie können auch die Stapel beseitigen (indem Sie "Suffix Maximums" und "Präfix -Minimum" berücksichtigen), aber die Stapel geben Ihnen die nächsten Elemente. Wenn Sie also Say $ ki $ minimieren wollten, können Sie die Stapel verwenden.

Pseudocode für den ersten Pass könnte so aussehen:

Stack <Pair<Elem, Index>> greats;
Elem auxArr[inputArr.Length];

for (Index i = 0; i < inputArr.Length; i++) {

    while (!greats.IsEmpty() && inputArr[i] > greats.PeekTop().Elem) {
        Pair top = greats.Pop();
        auxArr[top.Index] = i;
    }

    Pair p;
    p.Elem = inputArr[i];
    p.Index = i;

    greats.Push(p);
}