Czy istnieją rzeczywiste algorytmy, które znacznie przewyższają wyniki w poniższej klasie? [Zamknięte]

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 ² ) 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?

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.

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

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

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.

Dla praktycznych wartości ntak. 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.

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.

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.

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

O(1)Algorytm:

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

O(n)Algorytm:

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Oczywiście, dla każdej wartości n, gdzie n < one_millionThe O(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:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Państwo musi znać stałych i współczynników w swojej Owypowiedzi, a pan musi wiedzieć oczekiwany zakres n, 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 nw oczekiwanym zakresie, aby ustalić a posteriori, który algorytm okazał się szybszy.

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.

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.

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

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.

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óż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, jak containsi dlatego addwszystkie 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, containsi remove.

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

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:

W praktyce algorytm Schönhage – Strassen zaczyna przewyższać starsze metody, takie jak mnożenie Karatsuba i Toom – Cook dla liczb przekraczających 2 ^ 2 ^ 15 do 2 ^ 2 ^ 17 (10 000 do 40 000 cyfr dziesiętnych). [4] [5] [6 ]

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.

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

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.

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.

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.