Ostatniej nocy dyskutowałem z innym programistą, że nawet jeśli coś może być O (1), operacja, która jest O (n), może przewyższyć to, jeśli w algorytmie O (1) jest duża stała. Nie zgodził się, więc przyniosłem to tutaj.
Czy istnieją przykłady algorytmów, które znacznie przewyższają algorytmy w klasie poniżej? Na przykład O (n) jest szybsze niż O (1) lub O (n 2 ) jest szybsze niż O (n).
Matematycznie można to wykazać dla funkcji z asymptotycznymi górnymi granicami, gdy pomija się stałe czynniki, ale czy takie algorytmy istnieją na wolności? A gdzie znajdę ich przykłady? Do jakiego rodzaju sytuacji są używane?
algorithms
big-o
KyleWpppd
źródło
źródło
n
wystarczająco duży, aby skompensować stałą (co jest punktem notacji big-O).Odpowiedzi:
Wyszukiwanie w bardzo małych, stałych tabelach danych. Zoptymalizowana tabela skrótów może być O (1), a jednak wolniejsza niż wyszukiwanie binarne lub nawet wyszukiwanie liniowe ze względu na koszt obliczeń skrótu.
źródło
Mnożenie macierzy. Naiwny algorytm O (n ^ 3) jest często stosowany w praktyce jako szybszy niż O (n ^ 2.8) Strassena w przypadku macierzy małych; i dla większych matryc stosuje się Strassena zamiast algorytmu Coppersmitha-Winograda O (n ^ 2.3).
źródło
Prostym przykładem jest różnica między różnymi algorytmami sortowania. Mergesort, Heapsort i niektóre inne to O (n log n) . Quicksort to najgorszy przypadek O (n ^ 2) . Ale często Quicksort jest szybszy i faktycznie działa średnio jak O (n log n) . Więcej informacji .
Innym przykładem jest generowanie pojedynczej liczby Fibonacciego. Algorytm iteracyjny to O (n) , podczas gdy algorytm oparty na macierzy to O (log n) . Jednak dla pierwszych kilku tysięcy liczb Fibonacciego algorytm iteracyjny jest prawdopodobnie szybszy. Zależy to również oczywiście od wdrożenia!
Algorytmy o lepszej wydajności asymptotycznej mogą zawierać kosztowne operacje, które nie są konieczne w przypadku algorytmu o gorszej wydajności, ale prostsze operacje. Ostatecznie O- notacja mówi nam coś o wydajności tylko wtedy, gdy argument, na którym działa, dramatycznie wzrasta (zbliża się do nieskończoności).
źródło
Uwaga: Proszę przeczytać komentarze @ back2dos poniżej i innych guru, ponieważ są one w rzeczywistości bardziej pomocne niż to, co napisałem - Dziękuję wszystkim uczestnikom.
Myślę, że z poniższej tabeli (zaczerpniętej z: Big O notation , szukaj „The Pesesistic Nature of Algorytms:”), widać, że O (log n) nie zawsze jest lepsze niż powiedz, O (n). Myślę, że twój argument jest ważny.
źródło
y = 1
,y = log x
itd., A przecięciey = 1
iy = x
jest właśnie punktem(1,1)
. Gdyby to naprawdę było poprawne, niż by to powiedziało, algorytmy o wyższej złożoności mogą być szybsze dla 0 do 2 wpisów, co jest czymś, o co ludzie nie dbają. To, czego wykres całkowicie nie bierze pod uwagę (i z czego wynika zauważalna różnica w wydajności), to czynniki stałe.Dla praktycznych wartości
n
tak. To często pojawia się w teorii CS. Często istnieje skomplikowany algorytm, który ma technicznie lepszą wydajność big-Oh, ale stałe czynniki są tak duże, że sprawiają, że jest to niepraktyczne.Kiedyś mój profesor geometrii obliczeniowej opisał algorytm do triangulacji wielokąta w czasie liniowym, ale skończył z „bardzo skomplikowanym. Nie sądzę, żeby ktokolwiek go zaimplementował” (!!).
Ponadto kupy Fibonacciego mają lepsze właściwości niż normalne kupy, ale nie są zbyt popularne, ponieważ nie sprawdzają się w praktyce tak dobrze, jak zwykłe kupy. Może to kaskadować z innymi algorytmami stosującymi hałdy - na przykład najkrótsze ścieżki Dijkstry są matematycznie szybsze ze stertą Fibonacciego, ale zwykle nie w praktyce.
źródło
Porównaj wstawianie do połączonej listy i wstawianie do tablicy o zmiennym rozmiarze.
Ilość danych musi być dość duża, aby wstawienie listy połączonej O (1) było opłacalne.
Połączona lista ma dodatkowe koszty dla następnych wskaźników i dereferencji. Macierz o zmiennym rozmiarze musi kopiować dane. Kopiowanie to O (n), ale w praktyce bardzo szybkie.
źródło
Notacja Big-Oh jest używana do opisania tempa wzrostu funkcji, więc możliwe jest, że algorytm O (1) będzie szybszy, ale tylko do pewnego punktu (współczynnik stały).
Wspólne notacje:
O (1) - Liczba iteracji (czasem można to nazywać czasem spędzonym przez funkcję przez użytkownika) nie zależy od wielkości danych wejściowych i jest w rzeczywistości stała.
O (n) - Liczba iteracji rośnie liniowo proporcjonalnie do wielkości danych wejściowych. Znaczenie - jeśli algorytm iteruje przez dowolne wejście N, 2 * N razy, nadal jest uważany za O (n).
O (n ^ 2) (kwadrat) - Liczba iteracji jest kwadratem wielkości wejściowej.
źródło
Biblioteki Regex są zwykle implementowane w celu wykonywania wstecznego śledzenia, który ma najgorszy przypadek w czasie wykładniczym, zamiast generowania DFA o złożoności
O(nm)
.Naiwne cofanie może być skuteczniejsze, gdy dane wejściowe pozostają na szybkiej ścieżce lub zawodzą bez konieczności nadmiernego cofania.
(Chociaż ta decyzja nie opiera się wyłącznie na wydajności, umożliwia także cofanie odwołań).
źródło
O(1)
Algorytm:O(n)
Algorytm:Oczywiście, dla każdej wartości
n
, gdzien < one_million
TheO(n)
algorytm podano w przykładzie będzie szybciej niżO(1)
algorytmu.Chociaż ten przykład jest nieco żartobliwy, w duchu jest równoważny z następującym przykładem:
Państwo musi znać stałych i współczynników w swojej
O
wypowiedzi, a pan musi wiedzieć oczekiwany zakresn
, w celu określenia a priori , która zakończy się algorytm jest szybszy.W przeciwnym razie musisz porównać dwa algorytmy z wartościami
n
w oczekiwanym zakresie, aby ustalić a posteriori, który algorytm okazał się szybszy.źródło
Sortowanie:
Sortowanie wstawiane to O (n ^ 2), ale przewyższa inne algorytmy sortowania O (n * log (n)) dla niewielkiej liczby elementów.
To jest powód, dla którego większość implementacji sortowania używa kombinacji dwóch algorytmów. Np. Użyj sortowania scalającego, aby rozbić duże tablice, dopóki nie osiągną określonego rozmiaru, następnie użyj sortowania wstawianego, aby posortować mniejsze jednostki i scalić je ponownie za pomocą sortowania scalającego.
Zobacz Timsort bieżącą domyślną implementację sortowania Python i Java 7, które używają tej techniki.
źródło
Unifikacja algorytm stosowany w praktyce jest wykładniczy w najgorszym przypadku, dla niektórych wejść patologicznych.
Istnieje algorytm unifikacji wielomianowej , ale w praktyce jest on zbyt wolny.
źródło
Bubblesort w pamięci może przewyższyć szybkie sortowanie, gdy program jest zamieniany na dysk lub musi czytać każdy element z dysku podczas porównywania.
Powinien to być przykład, do którego mógłby się odnosić.
źródło
Często bardziej zaawansowane algorytmy zakładają pewną (kosztowną) konfigurację. Jeśli potrzebujesz go uruchomić tylko raz, możesz skorzystać z metody brute-force.
Na przykład: wyszukiwanie binarne i wyszukiwanie tablicy skrótów są znacznie szybsze na wyszukiwanie niż wyszukiwanie liniowe, ale wymagają odpowiednio posortowania listy lub zbudowania tabeli skrótów.
Sortowanie będzie kosztować N log (N), a tablica skrótów będzie kosztować co najmniej N. Teraz, jeśli zamierzasz wykonywać setki lub tysiące wyszukiwań, jest to nadal amortyzacja oszczędności. Ale jeśli potrzebujesz tylko jednego lub dwóch wyszukiwań, sensowne może być po prostu wyszukiwanie liniowe i oszczędność kosztów uruchamiania.
źródło
Deszyfrowanie to często 0 (1). Na przykład przestrzeń na klucze dla DES to 2 ^ 56, więc odszyfrowanie dowolnej wiadomości jest operacją o stałym czasie. Po prostu masz tam współczynnik 2 ^ 56, więc jest to naprawdę duża stała.
źródło
Różne realizacje zestawów przychodzą mi do głowy. Jedną z najbardziej naiwnych jest implementacja go za pomocą wektora, co oznacza,
remove
że zarówno, jakcontains
i dlategoadd
wszystkie przyjmują O (N).Alternatywą jest zaimplementowanie go za pomocą skrótu ogólnego przeznaczenia, który odwzorowuje skróty wejściowe na wartości wejściowe. Taki zestaw realizacji występuje z O (1)
add
,contains
iremove
.Jeśli założymy, że N wynosi około 10, pierwsza implementacja jest prawdopodobnie szybsza. Aby znaleźć element, wystarczy porównać 10 wartości z jedną.
Druga implementacja będzie musiała rozpocząć wszelkiego rodzaju sprytne transformacje, które mogą być znacznie droższe, niż wykonanie 10 porównań. Przy tych wszystkich kosztach możesz nawet stracić pamięć podręczną, a wtedy tak naprawdę nie ma znaczenia, jak szybko Twoje rozwiązanie jest teoretycznie.
Nie oznacza to, że najgorsza implementacja, o której możesz pomyśleć, przewyższy porządną, jeśli N jest wystarczająco mała. Oznacza to po prostu dla wystarczająco małej liczby N, że naiwna implementacja, o niskim poziomie zajmowania miejsca i narzutach, może faktycznie wymagać mniej instrukcji i powodować mniej błędów pamięci podręcznej niż implementacja, która stawia skalowalność na pierwszym miejscu, a zatem będzie szybsza.
Nie możesz naprawdę wiedzieć, jak szybko coś jest w scenariuszu ze świata rzeczywistego, dopóki nie umieścisz go w jednym i nie zmierzysz. Często wyniki są zaskakujące (przynajmniej dla mnie).
źródło
Tak, dla odpowiednio małego N. Zawsze będzie N, powyżej którego zawsze będziesz mieć porządek O (1) <O (lg N) <O (N) <O (N log N) <O (N ^ c ) <O (c ^ N) (gdzie O (1) <O (lg N) oznacza, że w algorytmie O (1) zajmie mniej operacji, gdy N jest odpowiednio duże, a c jest pewną stałą stałą, która jest większa niż 1 ).
Powiedzmy, że określony algorytm O (1) wymaga dokładnie f (N) = 10 ^ 100 (googol) operacji, a algorytm O (N) wymaga dokładnie g (N) = 2 N + 5 operacji. Algorytm O (N) da większą wydajność, dopóki N nie będzie z grubsza googolem (właściwie kiedy N> (10 ^ 100 - 5) / 2), więc jeśli spodziewałeś się, że N będzie w zakresie od 1000 do miliarda poniósłby poważną karę przy użyciu algorytmu O (1).
Lub dla realistycznego porównania, powiedzmy, że mnożycie liczby n-cyfrowe razem. Algorytm karacuby co najwyżej 3 n ^ (LG3) operacji (to jest w przybliżeniu O (n ^ 1,585)), podczas gdy algorytm Schönhage-Strassen O (N log n Log N), który jest szybszy celu , ale środki wikipedia:
Więc jeśli mnożycie razem 500 cyfr, nie ma sensu używać algorytmu, który jest „szybszy” przez duże argumenty O.
EDYCJA: Możesz znaleźć określenie f (N) w porównaniu g (N), biorąc limit N-> nieskończoność f (N) / g (N). Jeśli granica wynosi 0, to f (N) <g (N), jeśli granica jest nieskończonością, to f (N)> g (N), a jeśli granica jest jakąś inną stałą to f (N) ~ g (N) pod względem dużej notacji O.
źródło
Metoda simpleksowa dla programowania liniowego może być wykładnicza w najgorszym przypadku, podczas gdy stosunkowo nowe algorytmy punktu wewnętrznego mogą być wielomianowe.
Jednak w praktyce wykładniczy najgorszy przypadek dla metody simpleks nie pojawia się - metoda simplex jest szybka i niezawodna, podczas gdy wczesne algorytmy punktu wewnętrznego były zbyt wolne, aby były konkurencyjne. (Istnieją teraz bardziej nowoczesne algorytmy punktów wewnętrznych, które są konkurencyjne - ale metoda simpleks też jest ...)
źródło
Algorytmem Ukkonena do budowania prób sufiksów jest O (n log n). Ma tę zaletę, że jest „on-line” - to znaczy, że można stopniowo dodawać więcej tekstu.
Ostatnio inne bardziej złożone algorytmy twierdziły, że są szybsze w praktyce, głównie dlatego, że ich dostęp do pamięci ma większą lokalizację, co poprawia wykorzystanie pamięci podręcznej procesora i pozwala uniknąć zatrzymania potoku procesora. Zobacz np. Tę ankietę , która twierdzi, że 70–80% czasu przetwarzania spędza się na oczekiwaniu na pamięć, oraz ten artykuł opisujący algorytm „wotd”.
Próbki sufiksów są ważne w genetyce (do dopasowania sekwencji genów) i, nieco mniej ważne, w implementacji słowników Scrabble.
źródło
Zawsze istnieje najszybszy i najkrótszy algorytm dla każdego dobrze zdefiniowanego problemu . Jest to jednak tylko teoretycznie najszybszy algorytm (asymptotycznie).
Biorąc pod uwagę dowolny opis problemu P i instancją dla tego problemu I , to wylicza wszystkich możliwych algorytmów i dowody Pr , sprawdzanie każdej takiej pary czy Pr stanowi ważny dowód, że jest asymptotycznie najszybszy algorytm P . Jeśli stwierdzi takiego dowodu, to następnie wykonuje A na I .
Poszukiwanie tej odpornej na problemy pary ma złożoność O (1) (dla stałego problemu P ), więc zawsze używasz asymptotycznie najszybszego algorytmu dla problemu. Ponieważ jednak ta stała jest tak niewymownie ogromna w prawie wszystkich przypadkach, metoda ta jest całkowicie bezużyteczna w praktyce.
źródło
Wiele języków / frameworków używa naiwnego dopasowywania wzorców do dopasowywania ciągów zamiast KMP . Szukamy ciągów takich jak Tom, Nowy Jork, a nie ababaabababababaababababababab.
źródło