Czy istnieje algorytm, który wyszukuje posortowane podsekwencje wielkości trzy w czasie

Chcę udowodnić lub obalić istnienie algorytmu, który, biorąc pod uwagę tablicę $A$ liczb całkowitych, znajduje trzy indeksy $i, j$ i $k$ takie, że $i < j < k$ i $A[i] < A[j] < A[k]$ (lub stwierdza, że ​​nie ma takiej potrójnej) w czasie liniowym.

To nie jest zadanie domowe; Widziałem to na forum programistycznym sformułowanym jako „spróbuj wdrożyć taki algorytm”. Podejrzewam, że jest to niemożliwe po różnych eksperymentach. Moja intuicja mi to mówi, ale tak naprawdę to na nic się nie liczy.

Chciałbym to udowodnić formalnie. Jak ty to robisz? Idealnie chciałbym zobaczyć dowód ułożony krok po kroku, a następnie, jeśli masz taką skłonność, wyjaśnienie, w jaki sposób można ogólnie udowodnić / obalić takie proste pytania. Jeśli to pomaga, kilka przykładów:

[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)

Przypuszczałem, że można iterować po i za każdym razem, gdy występuje i < j (czyli nasze obecne j ), tworzymy nowy potrójny i wypychamy go na tablicę. Kontynuujemy kroczenie i porównywanie każdego potrójnego, dopóki jedna z naszych potrójnych nie zostanie ukończona. Więc jak to jest , ! Ale myślę, że jest to bardziej złożone niż zwykłe O ( n ), ponieważ liczba potrójnych w naszej potrójnej tablicy odpowiada w najgorszym przypadku wielkości listy wejściowej.$A$$i < j$$j$[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$\mathcal{O}(n)$

Jest to wariant problemu Najdłużej rosnącego podsekwencji ; jest to rozwiązanie przedstawione na Wikipedii za pomocą dwóch pomocniczych tablic i P :$M$$P$

• - przechowuje pozycję k najmniejszej wartości A [ k ], tak że istnieje rosnąca podsekwencja długości j kończąca się na A [ k ] w zakresie k ≤ i (uwaga: tutaj mamy j ≤ k ≤ i , ponieważ j reprezentuje długość rosnącego podsekwencji, a k reprezentuje pozycję jego zakończenia. Oczywiście, nigdy nie możemy mieć rosnącej podsekwencji długości 13 kończącej się w pozycji$M[j]$$k$$A[k]$$j$$A[k]$$k \leq i$$j \leq k \leq i$$j$$k$$13$$11$. z definicji).$k \leq i$

• - przechowuje pozycję poprzednika A [ k ] w najdłużej rosnącym podsekwencji kończącym się na A [ k ] .$P[k]$$A[k]$$A[k]$

  Ponadto algorytm przechowuje zmienną reprezentującą długość najdłuższego rosnącego podsekwencji znalezionego do tej pory.$L$

Algorytm działa w najgorszym przypadku . Twój problem jest szczególnym przypadkiem, który pozwala powrócić, gdy L = 3, które popycha środowisko wykonawcze w dół do O ( n ), ponieważ wyszukiwanie binarne działa tylko na tablicach o długości co najwyżej dwóch, czyli w czasie O ( 1 ) w przeciwieństwie do Θ ( log n ) w ogólnym przypadku.$\Theta(n\log n)$$L=3$$O(n)$$O(1)$$\Theta(\log n)$

Rozważ zmodyfikowany pseudo kod:

 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.

Uwaga na temat metodologii

Pomyślałem trochę o tym problemie i doszedłem do rozwiązania. Kiedy przeczytałem odpowiedź Saeeda Amiriego , zdałem sobie sprawę, że wymyśliłem specjalną wersję standardowego najdłuższego algorytmu znajdowania podsekwencji dla sekwencji długości 3. Podaję sposób, w jaki wymyśliłem rozwiązanie, ponieważ tak myślę jest interesującym przykładem rozwiązywania problemów.

Wersja dwuelementowa

Zacznijmy od małego: zamiast szukać trzech wskaźników, w których elementy są w porządku, spójrzmy na dwa: takie, że A [ i ] < A [ j ] .$i < j$$A[i] < A[j]$

Jeśli maleje (tj. ∀ i < j , A [ i ] ≥ A [ j ] lub równoważnie ∀ i , A [ i ] ≥ A [ i + 1 ] ), to nie ma takich wskaźników. W przeciwnym razie istnieje indeks i taki, że A [ i ] < A [ i + 1 ] .$A$$\forall i < j, A[i] \ge A[j]$$\forall i, A[i] \ge A[i+1]$$i$$A[i] < A[i+1]$

Ta sprawa jest bardzo prosta; postaramy się to uogólnić. Pokazuje, że opisany problem nie jest do rozwiązania: wymagane wskaźniki nie zawsze istnieją. Poprosimy więc raczej, aby algorytm zwrócił prawidłowe indeksy, jeśli istnieją, lub poprawnie twierdzi, że takich indeksów nie ma.

Wymyślanie algorytmu

Użyję terminu podsekwencja, aby oznaczać wyciąg z tablicy składający się z indeksów, które mogą nie być następujące po sobie ( ( A [ i 1 ] , … , A [ i m ] ) z i 1 < ⋯ < i m ), i uruchomić oznacza kolejne elementy A ( ( A [ i ] , A [ i + 1 ] , … , $A$$(A[i_1],\ldots,A[i_m])$$i_1 < \dots < i_m$$A$ ).$(A[i],A[i+1],\ldots,A[i+m-1])$

Właśnie widzieliśmy, że wymagane wskaźniki nie zawsze istnieją. Naszą strategią jest badanie, gdy wskaźniki nie istnieją. Zrobimy to, zakładając, że próbujemy znaleźć wskaźniki i zobaczyć, jak nasze wyszukiwanie może się nie udać. Wtedy przypadki, w których wyszukiwanie się nie powiedzie, zapewnią algorytm do znalezienia wskaźników.

Dzięki dwóm indeksom możemy znaleźć kolejne indeksy. Przy trzech indeksach możemy nie być w stanie wymyślić i k = j + 1 . Możemy jednak rozważyć przypadek rozwiązania szeregu trzech ściśle rosnących elementów ( A [ i ] < A [ i + 1 ] < A [ i + 2 ] ), ponieważ łatwo jest rozpoznać takie przebiegi, i zobacz, jak ten warunek może nie zostać spełniony. Załóżmy, że sekwencja nie ma ściśle rosnącego ciągu długości 3.$j=i+1$$k=j+1$$A[i] < A[i+1] < A[i+2]$

Sekwencja ma tylko ściśle rosnące przebiegi o długości 2 (które nazywam parami uporządkowanymi w skrócie), oddzielone malejącym przebiegiem długości co najmniej 2. W celu ściśle zwiększającego się przebiegu aby być częścią rosnącej sekwencji 3-elementowej, musi istnieć wcześniejszy element i taki, że A [ i ] < A [ j ] lub późniejszy element k taki, że A [ j + 1 ] < A [ $A[j] < A[j+1]$$i$$A[i] < A[j]$$k$ .$A[j+1] < A[k]$

Przypadek, w którym nie ma ani ani k , ma miejsce, gdy każda uporządkowana para jest całkowicie niższa niż następna. To nie wszystko: kiedy pary są przeplatane, musimy je dokładniej porównać.$i$$k$

Najbardziej wysunięty w lewo element rosnącego podsekwencji musi przyjść wcześnie i być mały. Następny element j musi być większy, ale możliwie najmniejszy, aby móc znaleźć trzeci większy element k . Pierwszy element i nie zawsze jest najmniejszym elementem w sekwencji i nie zawsze jest to pierwszy element, dla którego istnieje kolejny większy element - czasami jest dalej niższa 2-elementowa podsekwencja, a czasem jest lepsza pasuje do już znalezionego minimum.$i$$j$$k$$i$

Przechodząc od lewej do prawej, wstępnie wybieramy najmniejszy element jako . Jeśli znajdziemy większy element dalej w prawo, wybieramy tę parę jako próbną ( i , j ) . Jeśli znajdziemy jeszcze większy k , wygraliśmy. Kluczową rzeczą do zapamiętania jest to, że nasz wybór i i nasz wybór ( i , j ) są aktualizowane niezależnie: jeśli mamy kandydata ( i , j ) i stwierdzimy, że i ′ > j , że A [ i ′ ] < A $i$$(i,j)$$k$$i$$(i,j)$$(i,j)$$i' > j$ , i ′ zostaje kolejnym kandydatem i, ale ( i , j ) pozostaje. Tylko jeśli znajdziemy j ′ takie, że A [ j ′ ] < A [ j ] stanie się ( i ′ , j ′ ) nową parą kandydatów.$A[i'] < A[i]$$i'$$i$$(i,j)$$j'$$A[j'] < A[j]$$(i',j')$

Oświadczenie algorytmu

Podany w składni Pythona, ale uwaga, że ​​go nie testowałem.

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

Szkic próbny

index1jest indeksem minimalnej części tablicy, która została już przemierzona (jeśli występuje kilka razy, zachowujemy pierwsze wystąpienie) lub Noneprzed przetworzeniem pierwszego elementu. index2przechowuje wskaźniki rosnącej podsekwencji o długości 2 w już przemierzonej części tablicy, która ma najniższy największy element lub Nonejeśli taka sekwencja nie istnieje.

Kiedy return (index2[0], index2[1], i)uruchamia się, mamy value2[0] < value[1](jest to niezmiennik value2) i value[1] < A[i](oczywiste z kontekstu). Jeśli pętla kończy się bez wywoływania wczesnego powrotu, value1 == Nonew takim przypadku nie ma rosnącego podsekwencji o długości 2, nie mówiąc już o 3, lub value1zawiera rosnącą podsekwencję o długości 2, która ma najniższy największy element. W tym drugim przypadku mamy ponadto niezmienność, że żadna rosnąca podsekwencja długości 3 nie kończy się wcześniej niż value1; dlatego ostatni element każdego takiego podsekwencji, dodany do value2, tworzy rosnący podsekwencja o długości 3: ponieważ mamy również niezmiennik, który value2nie jest częścią rosnącego podsekwencji o długości 3 zawartej w już przemierzonej części tablicy, tam nie ma takiego podsekwencji w całej tablicy.

Udowodnienie wyżej wymienionych niezmienników pozostaje ćwiczeniem dla czytelnika.

Złożoność

$O(1)$$O(1)$$O(n)$

Formalny dowód

Pozostawione jako ćwiczenie dla czytelnika.

$O(n)$$O(n)$ .

Najpierw przejdź przez tablicę od lewej do prawej, utrzymując stos i tablicę pomocniczą, która informuje dla każdego elementu o indeksie elementu większego od niego i na prawo od niego.

$-1$

Za każdym razem, gdy rozważasz nowy element w tablicy, jeśli ten element jest większy niż górny element stosu, zrywasz go ze stosu i ustawiasz element tablicy pomocniczej odpowiadający górze, aby indeks nowego elementu był poniżej wynagrodzenie.

Kontynuuj usuwanie elementów ze stosu i ustawianie odpowiedniego indeksu, podczas gdy bieżący element jest większy. Gdy góra ma element, który nie jest mniejszy (lub staje się pusty), wepchnij bieżący element na stos i przejdź do następnego elementu tablicy, powtarzając powyższy krok.

Wykonaj kolejne przejście (i kolejną tablicę Aux), ale idąc od prawej do lewej.

$-1$ .

$O(n)$ .

$k-i$ , możesz użyć stosów.

Pseudo kod dla pierwszego przejścia może wyglądać następująco:

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);
}