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:
- 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)
- Każda tablica wejściowa gwarantuje odpowiedź
- największy oznacza, że element musi być większy niż każdy inny element
- 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.
algorithms
time-complexity
sets
transitivity
James Wierzba
źródło
źródło
Odpowiedzi:
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:
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).< ai j≠i ai>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< < #ai ai ai>?aj ai>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<n−1 ai<aj o(n2)
źródło
n
porównaniach, twoje obecne maksimum musi być odpowiedziąmax
moż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).Jak zauważa Ariel , standardowy algorytm maksymalnego wyszukiwania podany poniżej:
będzie działać bez modyfikacji, o ile:
(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 > y
jest zawsze fałszywy jeśli elementyx
iy
są nieporównywalne.)W szczególności twoje twierdzenie, że:
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:
x
momencie iteracja będzie elementem maksymalnym;m
będzie elementem maksymalnym; im
że nie zmieni się on w żadnej z kolejnych iteracji.Dlatego na końcu pętli
m
zawsze 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:
(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ównaniex > m
w kroku 2 powinno zostać zastąpione przezx ≠ 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:
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óciNone
.Gdybyśmy przechowywany indeks
m
w tablicy wejścioweja
, mogliśmy rzeczywiście zoptymalizować krok 2, aby sprawdzić tylko te elementy, które przychodzą przedm
sięa
, ponieważ wszelkie późniejsze elementy zostały już w porównaniu zm
w kroku 1. Ale to optymalizacja nie zmienia czasu złożoności asymptotycznej algorytmu, który wciąż jest O ( n ).źródło
if x > m:
jest niezdefiniowana.„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.
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.
źródło
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
źródło
else if
był potrzebny. Nie można go uruchomić, jeślimax
jest to maksimum, a jeśli maksimum nie zostało jeszcze spełnione, nie ma znaczenia, jaka jest wartośćmax
.if
bezelse
s? To tylko nawyk:else
nawet nie porównujemy. :)max
dowolny element listy i zrobić to wewnątrz pętliif 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)?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ę.
źródło
A > B
źródło