w czasie O (n): Znajdź największy element w zestawie, w którym porównanie nie jest przechodnie

Tytuł zawiera pytanie.

Jako dane wejściowe mamy listę elementów, które możemy porównać (określić, która jest największa ). Żaden element nie może być równy.

Kluczowe punkty:

1. Porównanie nie jest przechodnie (pomyśl o papierowych nożycach): może to być prawda: A> B, B> C, C> A (zwróć uwagę, że nie jest to poprawny wpis, ponieważ nie ma tutaj poprawnej odpowiedzi, opisuję tylko to, co „ porównanie nieprzechodnie ”oznacza)
2. Każda tablica wejściowa gwarantuje odpowiedź
3. największy oznacza, że ​​element musi być większy niż każdy inny element
4. Właściwość Converse tzn. A> B oznacza, że ​​B <A

Przykład:

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

Nie mogę znaleźć sposobu na zrobienie tego w czasie O (n), moim najlepszym rozwiązaniem jest O (n ^ 2).

Utknąłem na każdym podejściu, ponieważ aby być pewnym odpowiedzi, element musi być wyraźnie porównany z każdym innym elementem, aby udowodnić, że rzeczywiście jest odpowiedzią (ponieważ porównanie nie jest przechodnie).

Wyklucza to użycie sterty, sortowania itp.

Standardowy algorytm znajdowania maksimum nadal działa. Start z i przejść nad elementami, jeśli widzisz większą wartość, aktualizuje się, że maksymalną wartość. Powodem tego jest to, że każdy pominięty element jest mniejszy niż co najmniej jeden element, a zatem nie może być wartością maksymalną.$a_1$

Dla jasności, przez „standardowy algorytm” rozumiem, co następuje:

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

Dla kompletności omówię tutaj kwestie poruszone w komentarzach. Ustawienie w powyższej dyskusji jest znalezienie maksymalnej względem anty relacja symetryczna , gdzie i jest maksymalna, gdy dla wszystkich j ≠ i mamy do í > do j . Powyższy algorytm działa przy założeniu, że istnieje maksimum, jednak jeśli nie jest to znane, można go użyć do zweryfikowania istnienia maksimum (sprawdź, czy zwracany element jest rzeczywiście większy niż wszystkie inne elementy, jest to wspomniane w komentarzu Chi oraz w odpowiedzi Ilmari Karonen).$<$$a_i$$j\neq i$$a_i>a_j$

Jeśli niekoniecznie jest antysymetryczny, to powyższy algorytm zawodzi (jak wspomniał Emil w komentarzach). Jeśli < jest relacją arbitralną (tzn. Rozluźniamy zarówno przechodniość, jak i anty symetrię), nie jest trudno wykazać, że znalezienie maksimum w czasie liniowym nie jest możliwe. Oznaczmy przez # i ile razy i uczestniczył w zapytaniu, definiujemy relację kontradyktoryjnego w taki sposób, że maksymalna nie mogą być ujawnione bez wystarczającej ilości zapytań. Zważywszy na zapytanie I > ? a j , odpowiedz a i > a j jeśli # a $<$$<$$\#a_i$$a_i$$a_i >?a_j$$a_i>a_j$ i I < J inaczej. Jeśli liczba zapytań wynosi o ( n 2 ) , wówczas maksimum nie było jeszcze widoczne i można ustawić, aby był jednym z elementów zestawu.$\# a_i < n-1$$a_i<a_j$$o(n^2)$

Jak zauważa Ariel , standardowy algorytm maksymalnego wyszukiwania podany poniżej:

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

będzie działać bez modyfikacji, o ile:

• dowolna para elementów może być porównywana, oraz
• wejście gwarantuje, że zawiera maksymalny element, tj. element, który jest parowany większy niż jakikolwiek inny element na wejściu.

^{(Pierwsze założenie powyżej rzeczywiście mogą zostać złagodzone, nawet bez konieczności modyfikacji algorytmu, o ile założymy, że element ilość jest porównywalna z każdym innym pierwiastkiem, a które x > yjest zawsze fałszywy jeśli elementy xi ysą nieporównywalne.)}

W szczególności twoje twierdzenie, że:

[…] Dla pewności odpowiedzi element musi zostać wyraźnie porównany z każdym innym elementem (ponieważ porównanie nie jest przechodnie).

nie jest prawdą przy powyższych założeniach. W rzeczywistości, aby udowodnić, że powyższy algorytm zawsze znajdzie element maksymalny, wystarczy zauważyć, że:

1. ponieważ pętla iteruje wszystkie elementy wejściowe, w pewnym xmomencie iteracja będzie elementem maksymalnym;
2. ponieważ maksymalny element jest parami większy niż każdy inny element, wynika z tego, że pod koniec tej iteracji mbędzie elementem maksymalnym; i
3. ponieważ żaden inny element nie może być większy parą niż element maksymalny, wynika z tego, mże nie zmieni się on w żadnej z kolejnych iteracji.

Dlatego na końcu pętli mzawsze będzie maksymalny element, jeśli wejście zawiera jeden.

Ps. Jeśli wejście jest nie koniecznie zawsze zawiera element maksymalny, a następnie weryfikacji tego faktu będzie rzeczywiście wymaga testowania odpowiedź kandydata przed każdym innym elemencie, aby upewnić się, że jest to naprawdę maksymalne. Jednak nadal możemy to zrobić w czasie O ( n ) po uruchomieniu algorytmu maksymalnego wyszukiwania powyżej:

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

^{(Zakładam tutaj, że relacja >jest nierefleksyjna, tzn. Żaden element nie może być większy od siebie. Jeśli nie jest to koniecznie, porównanie x > mw kroku 2 powinno zostać zastąpione przez x ≠ m and x > m, gdzie ≠oznacza porównanie tożsamości. Lub możemy po prostu zastosować optymalizację zanotowano poniżej.)}

Aby udowodnić poprawność tej odmiany algorytmu, rozważ dwa możliwe przypadki:

• Jeśli dane wejściowe zawierają maksymalny element, krok 1 go znajdzie (jak pokazano powyżej), a krok 2 to potwierdzi.
• Jeśli dane wejściowe nie zawierają elementu maksymalnego, wówczas krok 1 zakończy wybieranie dowolnego elementu jako m. Nie ma znaczenia, który to element, ponieważ w każdym razie nie będzie on maksymalny, a zatem krok 2 wykryje to i wróci None.

Gdybyśmy przechowywany indeks mw tablicy wejściowej a, mogliśmy rzeczywiście zoptymalizować krok 2, aby sprawdzić tylko te elementy, które przychodzą przed msię a, ponieważ wszelkie późniejsze elementy zostały już w porównaniu z mw kroku 1. Ale to optymalizacja nie zmienia czasu złożoności asymptotycznej algorytmu, który wciąż jest O ( n ).

„największy oznacza, że ​​element musi być większy niż każdy inny element” to ogromna wskazówka, jak to zrobić w .$O(n)$

Jeśli przejrzysz listę elementów porównujących, każdy element, który „przegra” porównanie, może zostać natychmiast odrzucony, ponieważ aby był największy, musi być większy niż WSZYSTKIE inne elementy, aby pojedyncza strata go zdyskwalifikowała.

$n-1$

Rozwiązanie to umożliwia subtelność: „Żaden element nie może być równy” w połączeniu z faktem, że zawsze będzie największy element. Jeśli mapujemy relacje wygranych jako ukierunkowany wykres, jasne jest, że możemy osiągnąć największy element, po prostu podążając za wygranymi.

Zakładam, że relacja antysymetryczna dla co najmniej jednego elementu (co gwarantuje istnienie największego elementu), w przeciwnym razie zadanie jest niemożliwe. Jeśli wszystkie elementy w zestawie skończonym są porównywalne, wówczas działa zwykła procedura znajdowania maksimum.

Jeśli niektóre elementy nie są porównywalne, zadziała następująca procedura

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$

Mam nadzieję, że jest to nieco zrozumiałe. Zapytaj w komentarzach lub edytuj.

Podstawową ideą jest to, że nie możesz zebrać żadnych informacji o pozostałych elementach od tych, które już znasz, jeśli pozwalasz na całkowicie dowolną relację.

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

A > B$n$

$O(n)$