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

39

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?

KyleWpppd
źródło
15
Nawet w przypadku „dużych” algorytmów mniejszy niekoniecznie jest lepszy. Na przykład eliminacja gaussowska wynosi O (n ^ 3), ale istnieją algorytmy, które mogą to zrobić w O (n ^ 2), ale współczynnik dla algo kwadratu czasowego jest tak ogromny, że ludzie po prostu idą z O (n ^ 3) jeden.
BlackJack,
11
Musisz dodać „... do rzeczywistych problemów” lub coś takiego, aby to rozsądne pytanie. W przeciwnym razie musisz tylko zrobić nwystarczająco duży, aby skompensować stałą (co jest punktem notacji big-O).
starblue,
8
Nie bierz notacji Big-O dla prędkości.
Codism
16
Notacja big-O nie polega na tym, aby powiedzieć, jak szybko działa algorytm, ale jak dobrze się skaluje.
BlueRaja - Danny Pflughoeft
4
Dziwię się, że nikt nie wspomniał o algorytmie Simplex do rozwiązywania LP. Ma wykładniczy najgorszy przypadek z liniowym oczekiwanym czasem działania. W praktyce jest dość szybki. Zbudowanie problemu, który wykazuje najgorszy czas działania, jest banalne. Jest również intensywnie używany.
ccoakley,

Odpowiedzi:

45

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.

Loren Pechtel
źródło
14
Mówiąc dokładniej, hashtable lookup to O (m), gdzie m jest rozmiarem klucza. Możesz nazywać to O (1) tylko wtedy, gdy rozmiar klucza jest stały. Ponadto zazwyczaj jest to amortyzowane - w przeciwnym razie stół nie będzie się powiększał / kurczył. Drzewa trójskładnikowe często pokonują tabele skrótów dla wyszukiwania łańcuchów w kontekstach, w których łańcuchy dość często nie występują - wyszukiwanie drzewa trójskładnikowego często odkryje, że klucz nie jest obecny, wciąż sprawdzając pierwszy znak lub dwa ciągi, w których wersja hashtable nie obliczyła jeszcze skrótu.
Steve314,
2
Uwielbiam odpowiedź Lorena Pechtela i pierwszy komentarz Steve314. Tak naprawdę to widziałem. Jeśli utworzysz klasę Java, która ma metodę hashcode (), która zwraca zbyt długo wartość skrótu (i nie może / nie może jej buforować), to za pomocą instancji takiej klasy w kolekcji typu skrótu (np. HashSet) spowoduje, że kolekcja ALOT będzie wolniejsza niż kolekcja typu tablicowego (jak ArrayList).
Shivan Dragon,
1
@ Steve314: dlaczego zakładasz, że funkcjami skrótu są O (m), gdzie m jest wielkością klucza? Funkcje skrótu mogą być O (1), nawet jeśli masz do czynienia z łańcuchami (lub innym typem złożonym). Nie ma zbyt dużej wartości, aby umieścić ją w definicji formalnej, po prostu uświadomienie sobie, że funkcja skrótu może znacznie zmienić złożoność, jeśli wybrana zostanie niewłaściwa struktura danych (tabela skrótów) do wprowadzenia (rozmiar klucza jest nieprzewidywalny).
Codism
1
@ Steve314: Uwaga: powiedziałem, że naprawiłem tabele danych. Nie rosną. Ponadto wydajność O (1) można uzyskać z tabeli skrótów tylko wtedy, gdy można zoptymalizować klucz, aby upewnić się, że nie ma kolizji.
Loren Pechtel
1
@Loren - ściśle, jeśli stół ma ustalony rozmiar, istnieje stała maksymalna ilość czasu, którą możesz poświęcić na szukanie wolnego miejsca. Oznacza to, że co najwyżej możesz sprawdzić n-1 już wypełnione szczeliny, gdzie n jest stałym rozmiarem tabeli. Tak więc tablica skrótu o stałym rozmiarze jest w rzeczywistości O (1), bez potrzeby analizy amortyzowanej. Nie oznacza to, że nie przejmujesz się spowolnieniem dostępu w miarę zapełniania się stołu - tyle, że to nie to, co wyraża duże O.
Steve314,
25

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

Peter Taylor
źródło
2
Coppersmith-Winograd NIGDY nie jest używany. Jego wdrożenie byłoby okropnym zadaniem samym w sobie, a stała jest tak zła, że ​​byłaby niewykonalna nawet w przypadku problemów współczesnej matrycy naukowej.
tskuzzy
24

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

molf
źródło
To świetne wyjaśnienie Big-O, ale nie odnosi się do sedna pytania, które dotyczy konkretnych przypadków, w których algorytm O (n) będzie szybszy niż O (1).
KyleWpppd
Fibonacci numer jeden jest nieco wyłączony. Rozmiar wyjściowy jest wykładniczy w rozmiarze wejściowym, więc jest to różnica między O (lg n * e ^ n) a O (lg lg n * e ^ n).
Peter Taylor,
Dodatek: w najlepszym wypadku. Algorytm oparty na macierzach dokonuje mnożenia przez liczby rzędu 1,5 ^ n, więc O (lg lg n * ne ^ n) może być najlepszym możliwym do udowodnienia.
Peter Taylor,
1
Quicksort jest zwykle opisywany jako oczekiwana wydajność O (n log n) - najgorszy przypadek jest raczej mało prawdopodobny w przypadku losowych danych wejściowych, a wbudowanie pewnej losowości w przedrostek lub wybór osi przestawnej oznacza, że ​​najgorszy przypadek jest bardzo mało prawdopodobny w przypadku znacznych rozmiarów danych wejściowych. Najgorszy przypadek jest mniej istotny niż fakt, że quicksort jest (1) bardzo prosty i (2) bardzo przyjazny dla pamięci podręcznej, co prowadzi do znacznie lepszych stałych czynników niż w wielu innych algorytmach sortowania.
Steve314,
(2) jest właśnie rodzajem rozważań zewnętrznych, które należy wziąć pod uwagę, patrząc na wyniki dużej-O. Algorytmicznie, Mergesort powinien zawsze przewyższać Quicksort, ale użycie zasobów i lokalizacja pamięci podręcznej zasadniczo odwracają ich rzeczywiste pozycje wydajności.
Dan Lyons,
18

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.

Pic-1

Emmad Kareem
źródło
6
Pytanie wymagało konkretnych przykładów algorytmów ze świata rzeczywistego. To nie ma tak jak jest.
Megan Walker,
19
Na tym wykresie nie widać nic, co odpowiadałoby na pytanie. To jest mylące. Ten wykres przedstawia jedynie funkcje y = 1, y = log xitd., A przecięcie y = 1i y = xjest 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.
back2dos,
@Samuel Walker, dzięki za komentarz. Podany link (Link-1) zawiera kilka przykładów algorytmów według kategorii.
NoChance,
5
@ back2dos: Sam wykres nie odpowiada na pytanie, ale można na nie odpowiedzieć. Kształt każdej wyświetlanej funkcji jest taki sam dla dowolnej skali i stałego współczynnika. Dzięki temu wykres pokazuje, że przy danej kombinacji funkcji istnieje zakres danych wejściowych, dla których jedno jest mniejsze, oraz zakres danych wejściowych, dla których drugie jest.
Jan Hudec,
2
@dan_waterworth, masz rację, przyznam się do tego i usunę ten komentarz. Niemniej jednak odpowiedź jest niepoprawna lub myląca z dwóch względów: 1) Chodzi o to, że Big-O ma górną granicę złożoności; ma to znaczenie tylko dla dużego n, ponieważ wyraźnie odrzucamy mniejsze terminy, które są przytłoczone największym terminem, gdy n rośnie. 2) Celem pytania jest znalezienie przykładów dwóch algorytmów, w których ten z wyższą granicą Big-O przewyższa ten z dolną granicą. Ta odpowiedź kończy się niepowodzeniem, ponieważ nie podaje takich przykładów.
Caleb
11

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.

Gabe Moothart
źródło
Jest to szybsze w przypadku dużych wykresów rzędu około 100 000 wierzchołków.
tskuzzy
Kupy Fibonacciego były moją pierwszą (właściwie drugą) myślą.
Konrad Rudolph,
10

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.

Winston Ewert
źródło
1
Macierz o zmiennym rozmiarze jest podwajana za każdym razem, gdy się wypełnia, więc średni koszt zmiany rozmiaru na wstawienie wynosi O (1).
kevin cline
2
@kevincline, tak, ale O (n) wynika z konieczności przesunięcia wszystkich elementów za punktem wstawiania do przodu. Alokacja jest amortyzowana w czasie O (1). Chodzi mi o to, że ruch ten jest nadal bardzo szybki, więc w praktyce zwykle bije się powiązane listy.
Winston Ewert
Powodem, dla którego ciągłe tablice są tak szybkie w porównaniu z listami połączonymi, jest buforowanie procesora. Przejście do połączonej listy spowoduje brak pamięci podręcznej dla każdego elementu. Aby uzyskać to, co najlepsze z obu światów, należy użyć rozwijanej listy połączonej .
dan_waterworth
Macierze o zmiennym rozmiarze nie zawsze są kopiowane. To zależy od tego, na czym działa i czy coś jest na drodze. To samo dotyczy podwojenia rozmiaru, w zależności od implementacji. Problem z przewracaniem się jest jednak problemem. Listy połączone są zwykle najlepsze dla kolejek o nieznanym rozmiarze, chociaż bufory obrotowe dają kolejkom szansę na ich pieniądze. W innych przypadkach listy połączone są przydatne, ponieważ alokacja lub rozszerzenie po prostu nie pozwoli ci mieć ciągłych rzeczy przez cały czas, więc i tak potrzebujesz wskaźnika.
jgmjgm
@ jgmjgm, jeśli wstawisz do środka tablicy o zmiennym rozmiarze, to absolutnie kopiuje elementy po tym.
Winston Ewert
8

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.

Yam Marcovic
źródło
2
Aby dodać przykład do doskonałej odpowiedzi: metoda O (1) może zająć 37 lat na połączenie, podczas gdy metoda O (n) może zająć 16 * n mikrosekund na połączenie. Który jest szybszy?
Kaz Dragon,
16
Zupełnie nie rozumiem, jak to odpowiada na pytanie.
avakar
7
Rozumiem big-O. Nie rozwiązuje to rzeczywistego pytania, które jest konkretnymi przykładami funkcji, w których algorytmy o niższym big-O są lepsze niż te o wyższym big-O.
KyleWpppd
Kiedy umieścisz pytanie w formie „Czy istnieją przykłady ...”, ktoś nieuchronnie odpowie na „Tak”. bez podawania.
rakslice
1
@rakslice: Może tak. Jednak ta strona wymaga wyjaśnienia (lub jeszcze lepszego dowodu) wszelkich twoich wypowiedzi. Teraz najlepszym sposobem na udowodnienie, że są takie przykłady, jest podanie jednego;)
back2dos
6

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

dan_waterworth
źródło
Myślę, że jest to również częściowo historyczne - algorytm przekształcenia wyrażenia regularnego w DFA został opatentowany, gdy opracowywano niektóre z wcześniejszych narzędzi (chyba sed i grep). Oczywiście słyszałem o tym od mojego profesora od kompilatorów, który nie był do końca pewien, więc jest to konto z trzeciej ręki.
Tikhon Jelvis,
5

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.

yfeldblum
źródło
4

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.

OliverS
źródło
3

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

użytkownik1249
źródło
Czy cytowane złożoności dla szybkiego sortowania i bąbelkowego nie zakładają losowego dostępu do pamięci O (1)? Jeśli tak już nie jest, czy nie trzeba ponownie analizować złożoności szybkich sortowań?
Viktor Dahl,
@ ViktorDahl, czas dostępu do przedmiotu nie jest częścią tego, co jest tradycyjnie mierzone w złożoności algorytmu sortowania, więc „O (1)” nie jest tutaj właściwym wyborem słów. Zamiast tego użyj „stałego czasu”. PHK napisał jakiś czas temu artykuł o algorytmach sortowania, wiedząc, że niektóre elementy są droższe do odzyskania niż inne (pamięć wirtualna) - queue.acm.org/detail.cfm?id=1814327 - może być dla ciebie interesujące.
Teraz widzę swój błąd. Zazwyczaj mierzy się liczbę porównań i oczywiście prędkość nośnika pamięci nie ma na nie wpływu. Dziękuję również za link.
Viktor Dahl,
3

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.

rev Matthew Scouten
źródło
1

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.

Zachary K.
źródło
Nie jest deszyfrowanie wiadomości o O ( n ), gdzie n jest proporcjonalna do rozmiaru wiadomości? Dopóki masz odpowiedni klucz, rozmiar klucza nawet się nie bierze pod uwagę; niektóre algorytmy mają minimalne procesy konfiguracji / ekspansji kluczy lub nie mają ich wcale (DES, RSA - należy pamiętać, że generowanie kluczy może nadal być złożonym zadaniem, ale nie ma to nic wspólnego z rozszerzaniem klucza), podczas gdy inne są niezwykle złożone (przychodzi na myśl Blowfish), ale po zakończeniu czas na wykonanie rzeczywistej pracy jest proporcjonalny do wielkości wiadomości, stąd O (n).
CVn
Prawdopodobnie masz na myśli raczej kryptoanalizę niż deszyfrowanie?
lewo około
3
Cóż, tak, istnieje wiele rzeczy, które można uznać za stałe i zadeklarować algorytm jako O (1). [sortowanie domyślnie zakłada, że ​​porównanie elementów zajmuje stałą ilość czasu lub dowolną matematykę z liczbami innymi niż bignum]
Random832,
1

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

back2dos
źródło
1

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.

dr jimbob
źródło
1

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 konkurencyjne - ale metoda simpleks też jest ...)

nadchodząca burza
źródło
0

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.

Ed Staub
źródło
0

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.

Alex ten Brink
źródło
0

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.

Łukasz Madon
źródło