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

21

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.

James Wierzba
źródło
8
Nie jest jasne, jak zdefiniować „największy element”? Na przykład, który element jest największy, jeśli ? Czy masz jakieś inne zasady porównywania? ZA>b,b>do,do>ZA
fade2black,
6
Nie wyobrażam sobie, jak wybralibyśmy największy element w zestawie, który nie jest przynajmniej częściowo uporządkowany. Zobacz definicję największego i najmniejszego elementu. Brak przechodniości wyklucza częściowy porządek.
fade2black
3
@ fade2black Dlaczego łączysz mnie z inną definicją „największego”. Podaję wprost definicję największego w kontekście tego pytania. Świetne środki, element jest większy niż każdy inny element. Żaden element nie jest równy. To wszystko. Czy to nie jest jasne?
James Wierzba,
2
Twój ostatni przykład z A, B, C, D byłby pomocny w zrozumieniu twojego pytania, jeśli umieściłeś je w OP.
fade2black,
3
Członek zespołu kompilatora C # zadawał to pytanie jako pytanie do wywiadu; jest to istotne, ponieważ w języku C # algorytm rozwiązywania przeciążenia musi wybrać unikalny najlepszy element zestawu, biorąc pod uwagę relację „lepszości”, która jest zwykle, ale niekoniecznie przechodnia. (Lub udzielić odpowiedniej odpowiedzi, jeśli nie ma tak wyjątkowego najlepszego członka; możliwe są więzi.) Chociaż udało mi się odpowiedzieć poprawnie, nigdy nie myślałem, że to szczególnie dobre pytanie podczas rozmowy kwalifikacyjnej, ponieważ opiera się na wiedzy „aha”, aby uzyskać algorytm liniowy.
Eric Lippert,

Odpowiedzi:

38

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ą.a1

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).<aijiai>aj

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 i<<#aiaiai>?ajai>aj 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.#ai<n1ai<ajo(n2)

Ariel
źródło
1
@JamesWierzba (myślę) on po prostu oznacza, że ​​element „pominięty” to taki, który nie jest większy niż twoje obecne maks. Rozważ standardowy algorytm: każdą wartość na liście porównujesz z bieżącym maksimum. Powiedziałeś, że na każdej liście jest najlepszy element. W pewnym momencie porównasz to z bieżącym maksimum, a ponieważ jest ono większe, wartość ta staje się Twoim nowym maksimum. Ponieważ ta wartość jest większa niż wszystko inne na liście, nigdy nie znajdziesz elementu, który jest większy, a twoja największa wartość nie zostanie zastąpiona. Po twoich nporównaniach, twoje obecne maksimum musi być odpowiedzią
Lord Farquaad
1
Ten algorytm, edytowany dla jasności, nie zakłada przechodniości. Jeśli trudno ci w to uwierzyć, postępuj zgodnie ze szczegółami dowodu poprawności (załóż dla celów sprzeczności, że zwracana wartość nie jest wartością maksymalną, i skorzystaj z pomysłu z pierwszego akapitu).
Ariel,
7
Opiera się to na założeniu 2 w pytaniu: w tablicy zawsze jest maksimum. Gdyby tak nie było, maxmoże to być maksimum podtablicy. Mimo to, nawet bez założenia 2, można znaleźć wstępne maksimum, a następnie zweryfikować je na całej tablicy za pomocą drugiego skanu, w obrębie granicy O (n).
chi
7
Ta odpowiedź zakłada, że i B > A nie mogą trzymać się jednocześnie. O ile widzę, nie jest to wykluczone w pytaniu. ZA>bb>ZA
Emil Jeřábek wspiera Monikę
4
@ oconnor0 To nie następuje. Dla konkretnego przykładu załóżmy, że A> B, A> C, B> A i C> B.Wówczas A jest większy niż jakikolwiek inny element w zestawie (i jest jedynym elementem z tą właściwością), ale jeśli elementy są napotkany w kolejności A, B, C, algorytm wyświetli C.
Emil Jeřábek obsługuje Monikę
24

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

Ilmari Karonen
źródło
3
W rzeczywistości PO pomija wiele szczegółów. Na przykład nic nie mówi się o zwrotności relacji, więc jeśli nie jest ona zwrotna, to if x > m:jest niezdefiniowana.
fade2black
4

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

n1

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.

Danikow
źródło
1
Wykres acykliczny ” to zły model: zamiast tego powinien to być „ turniej ”. Cykle są dozwolone i ważne jest, aby każda krawędź istniała dokładnie w jednym kierunku.
Peter Taylor,
@PeterTaylor masz całkowitą rację, myślałem tylko o zwycięstwach, które prowadzą do elementu „największego”, pozostałe wygrane są mniej istotne, ale mogą zostać przekreślone na drodze do odkrycia największego, więc masz rację, że mogą ” t być dyskontowany
Danikov
3

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

ZA,b,do,re

ZA>b,b>do,do>ZA
re>ZA,re>b,re>do


ja=1: max=ZA
ja=2): max=ZAZA>b
i=3: max=CA<C
i=4: max=DD>C

m>aa<mamm<aamam

fade2black
źródło
Nie sądzę, żeby pierwszy else ifbył potrzebny. Nie można go uruchomić, jeśli maxjest to maksimum, a jeśli maksimum nie zostało jeszcze spełnione, nie ma znaczenia, jaka jest wartość max.
rici,
Tak, to jest pierwszy. Drugi to drugi :)
rici,
Masz na myśli zostawić ifbez elses? To tylko nawyk: elsenawet nie porównujemy. :)
fade2black,
1
Czy nie byłoby prościej po prostu zainicjować maxdowolny element listy i zrobić to wewnątrz pętli if max and a[i] are comparable and max < a[i] then max = a[i](gdzie pierwsza część warunku mogłaby zostać pominięta, jeśli założymy, że próba porównania dwóch nieporównywalnych elementów zawsze daje fałsz)?
Ilmari Karonen,
1
@badallen OP zakłada, że ​​zawsze jest największy element. W twoim przykładzie nie ma największego elementu.
fade2black
2

ZA<bb<ZA

ZA1...ZAnZAja<ZAjot

n2)

ZAja<ZAjotjot

jot0Ai<Aj0ijijAi<AjiijAij<Ajj0ij

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

Corinna
źródło
1

A > Bn

O(n)

maniak zapadkowy
źródło