Czy są jakieś przypadki, w których wolisz algorytm o wyższym stopniu złożoności niż O?

242

Czy są jakieś przypadki, w których wolisz O(log n)złożoność O(1)czasu niż złożoność czasu? A O(n)może O(log n)?

Czy masz jakieś przykłady?

V.Leymarie
źródło
67
Wolałbym O(log n)algorytm od O(1)algorytmu, jeśli rozumiem ten pierwszy, ale nie ten drugi ...
Codor
14
Istnieje mnóstwo niepraktycznych struktur danych z operacjami O (1) z teoretycznej informatyki. Jednym przykładem może być select () na wektorach bitowych, które mogą być obsługiwane w o (n) dodatkowej przestrzeni i O (1) na operację, przy użyciu 5 warstw pośrednich. Proste wyszukiwanie binarne w połączeniu z O (1) rank () okazuje się w praktyce szybsze według autora zwięzłej biblioteki struktury danych
Niklas B.
17
Niższa asymptotyczna złożoność nie gwarantuje szybszych czasów działania. Mnożenie macierzy badawczej dla konkretnego przykładu.
Connor Clark,
54
Ponadto ... każdy algorytm można przekonwertować na O (1), biorąc pod uwagę wystarczająco duży przegląd tabeli;)
Connor Clark
19
@Hoten - Zakładając, że wyszukiwanie tabel to O (1), co wcale nie jest dane dla wielkości tabel, o których mówisz! :)
Jander

Odpowiedzi:

267

Może być wiele powodów, aby preferować algorytm o większej złożoności czasu O niż niższy:

  • przez większość czasu niższa złożoność dużych O jest trudniejsza do osiągnięcia i wymaga wykwalifikowanej implementacji, dużej wiedzy i wielu testów.
  • big-O ukrywa szczegóły dotyczące stałej : algorytm, który działa, 10^5jest lepszy z punktu widzenia big-O niż 1/10^5 * log(n)( O(1)vs O(log(n)), ale dla najbardziej uzasadnionego npierwszy będzie działał lepiej. Na przykład najlepsza złożoność mnożenia macierzy jest O(n^2.373)taka, że ​​stała jest tak wysoka, że ​​(o ile mi wiadomo) biblioteki obliczeniowe jej nie wykorzystują.
  • big-O ma sens, gdy obliczasz coś dużego. Jeśli trzeba posortować tablicę trzech liczb, to naprawdę mało ważne czy używasz O(n*log(n))lub O(n^2)algorytm.
  • czasem przewaga złożoności małych liter może być naprawdę znikoma. Na przykład istnieje drzewo tango o strukturze danych, które zapewnia O(log log N)złożoność czasową znalezienia elementu, ale istnieje również drzewo binarne, które znajduje to samo O(log n). Nawet w przypadku ogromnych liczb n = 10^20różnica jest znikoma.
  • złożoność czasu to nie wszystko. Wyobraź sobie algorytm, który działa O(n^2)i wymaga O(n^2)pamięci. Może być preferowane w O(n^3)czasie i O(1)przestrzeni, gdy n nie jest tak naprawdę duże. Problem polega na tym, że możesz długo czekać, ale bardzo wątpię, czy uda ci się znaleźć pamięć RAM wystarczająco dużą, aby użyć jej z algorytmem
  • równoległość jest dobrą cechą w naszym rozproszonym świecie. Istnieją algorytmy, które można łatwo zrównoleglić, a niektóre nie są w ogóle równoległe. Czasami sensowne jest uruchomienie algorytmu na 1000 maszynach towarowych o większej złożoności niż przy użyciu jednej maszyny o nieco większej złożoności.
  • w niektórych miejscach (bezpieczeństwo) może być wymagana złożoność. Nikt nie chce mieć algorytmu haszującego, który potrafi haszować błyskawicznie szybko (bo wtedy inni ludzie mogą cię brutalnie zmusić)
  • chociaż nie jest to związane ze zmianą złożoności, ale niektóre funkcje bezpieczeństwa powinny być napisane w sposób zapobiegający atakowi czasowemu . Przeważnie pozostają w tej samej klasie złożoności, ale są modyfikowane w taki sposób, że zawsze dzieje się gorzej. Jednym z przykładów jest porównanie, że łańcuchy są równe. W większości aplikacji sensowne jest szybkie zerwanie, jeśli pierwsze bajty są różne, ale ze względów bezpieczeństwa nadal będziesz czekać na sam koniec, aby przekazać złe wieści.
  • ktoś opatentował algorytm o niższej złożoności i bardziej ekonomicznym rozwiązaniem jest stosowanie wyższej złożoności niż płacenie pieniędzy.
  • niektóre algorytmy dobrze dostosowują się do konkretnych sytuacji. Na przykład sortowanie wstawiania ma średnią złożoność czasową O(n^2), gorszą niż szybkie sortowanie lub scalanie, ale jako algorytm online może skutecznie sortować listę otrzymywanych wartości (jako dane wejściowe użytkownika), w przypadku gdy większość innych algorytmów może działać tylko wydajnie na pełnej liście wartości.
Salvador Dali
źródło
6
Widziałem także kilka razy, że ludzie koncentrowali się na dużej O swojego algorytmu centralnego, ale ignorowali koszty konfiguracji. Na przykład budowanie tabeli skrótów może być droższe niż przechodzenie przez tablicę liniowo, jeśli nie trzeba tego robić w kółko. W rzeczywistości, ze względu na sposób budowania współczesnych procesorów, nawet wyszukiwanie binarne może być tak samo szybkie na posortowanych tablicach, jak wyszukiwanie liniowe - profilowanie jest koniecznością.
Luaan,
@Luaan „W rzeczywistości, ze względu na sposób budowy nowoczesnych procesorów, nawet wyszukiwanie binarne może być tak samo szybkie w sortowanych tablicach jak wyszukiwanie liniowe - profilowanie jest koniecznością”. Ciekawy! Czy możesz wyjaśnić, w jaki sposób wyszukiwanie binarne i wyszukiwanie liniowe może zająć tyle samo czasu na nowoczesnym procesorze?
DJG,
3
@Luaan - Nieważne, znalazłem to: schani.wordpress.com/2010/04/30/linear-vs-binary-search
DJG
2
@DenisdeBernardy: Nie, w rzeczywistości tak nie jest. Mogą to być algorytmy w języku P. I nawet jeśli nie byłyby, przy rozsądnych definicjach tego, co oznacza równoległość, nie oznaczałoby to również P! = NP. Pamiętaj również, że wyszukiwanie przestrzeni możliwych przebiegów niedeterministycznej maszyny Turinga jest dość równoległe.
einpoklum
228

Zawsze istnieje ukryta stała, która może być niższa w algorytmie O (log n ). Dzięki temu może działać szybciej w praktyce dla rzeczywistych danych.

Istnieją również obawy dotyczące miejsca (np. Jazda na tosterze).

Istnieją również obawy dotyczące czasu programisty - O (log n ) może być 1000 × łatwiejszy do wdrożenia i weryfikacji.

Alistra
źródło
Fajnie, dziękuję. Pomyślałem, że warto rozważyć algorytm O (logn), aby zapewnić stabilność programu (np. W
samowyważących się
16
Jeden przykład, o którym mogę pomyśleć: w przypadku małej posortowanej tablicy programiści mogliby łatwiej zaimplementować funkcję wyszukiwania binarnego niż napisać pełną implementację mapy hash i użyć jej zamiast tego.
Pułkownik Trzydzieści Dwa
5
Przykład złożoności: znalezienie mediany nieposortowanej listy jest łatwe do zrobienia w O (n * log n), ale trudne do wykonania w O (n).
Paul Draper,
1
-1, nie umieszczaj dzienników w swoim tosterze ... Żartuję, to miejsce na miejscu. lg njest tak bardzo zbliżony do kdużego, nże większość operacji nigdy nie zauważy różnicy.
corsiKa,
3
Istnieje również fakt, że złożoność algorytmiczna, którą zna większość ludzi, nie uwzględnia efektów pamięci podręcznej. Wyszukiwanie czegoś w drzewie binarnym to według większości ludzi O (log2 (n)), ale w rzeczywistości jest znacznie gorzej, ponieważ drzewa binarne mają złą lokalizację.
Doval,
57

Dziwię się, że nikt jeszcze nie wspomniał o aplikacjach związanych z pamięcią.

Może istnieć algorytm, który ma mniej operacji zmiennoprzecinkowych z powodu jego złożoności (tj. O (1) < O (log n )) lub ponieważ stała przed złożonością jest mniejsza (tj. 2 n 2 <6 n 2 ) . Niezależnie od tego, nadal możesz preferować algorytm z większą ilością FLOP, jeśli niższy algorytm FLOP jest bardziej związany z pamięcią.

Rozumiem przez „związany z pamięcią” to, że często uzyskujesz dostęp do danych, które są stale poza pamięcią podręczną. Aby pobrać te dane, musisz pobrać pamięć z faktycznie pamięci do pamięci podręcznej, zanim będziesz mógł wykonać na niej operację. Ten krok pobierania jest często dość powolny - znacznie wolniejszy niż sama operacja.

Dlatego jeśli twój algorytm wymaga więcej operacji (ale operacje te są wykonywane na danych, które już znajdują się w pamięci podręcznej [i dlatego nie jest wymagane pobieranie]), nadal wykona algorytm przy mniejszej liczbie operacji (które muszą być wykonane poza -buforuj dane [i dlatego wymagają pobrania]) pod względem rzeczywistego czasu pracy.

NoseKnowsAll
źródło
1
Alistra zajęła się tym pośrednio, mówiąc o „obawach związanych z przestrzenią kosmiczną”
Zach Saucier,
2
Ogromna ilość pominiętych pamięci podręcznych tylko zwielokrotnia ostateczne wykonanie przez stałą wartość (która nie jest większa niż 8 dla 4-rdzeniowego procesora 3,2 GHz z ramem 1,6 GHz, zwykle jest znacznie niższa), więc jest liczona jako stała stała w dużym -O notacja. Zatem jedyną rzeczą, którą pamięć podręczna traci, jest przesunięcie progu n, w którym to rozwiązanie O (n) zaczyna być wolniejsze niż rozwiązanie O (1).
Marian Spanik,
1
@MarianSpanik Masz oczywiście rację. Pytanie to dotyczyło jednak sytuacji, w której wolelibyśmy O(logn)więcej O(1). Można bardzo łatwo wyobrazić sobie sytuację, w której dla wszystkich możliwych nzastosowań aplikacja działająca w mniejszej ilości pamięci działałaby szybciej, nawet przy większej złożoności.
NoseKnowsAll
@MarianSpanik nie brakuje pamięci podręcznej do 300 cykli zegara? Skąd pochodzi 8?
Mam nadzieję, że będzie
43

W kontekstach, w których bezpieczeństwo danych stanowi problem, bardziej złożony algorytm może być lepszy niż algorytm mniej złożony, jeśli bardziej złożony algorytm ma lepszą odporność na ataki czasowe .

Kevin K.
źródło
6
Podczas gdy to, co powiedziałeś, jest prawdą, w tym przypadku algorytm wykonywany w O (1) jest z definicji niewrażliwy na ataki czasowe.
Justin Lessard,
17
@JustinLessard: Bycie O (1) oznacza, że ​​istnieje pewien rozmiar wejściowy, po którym środowisko wykonawcze algorytmu jest ograniczone stałą. Co dzieje się poniżej tego progu jest nieznane. Ponadto próg może nawet nie zostać osiągnięty dla jakiegokolwiek użycia algorytmu w świecie rzeczywistym. Algorytm może być liniowy, a zatem na przykład wyciek informacji o długości danych wejściowych.
Jörg W Mittag,
12
Środowisko wykonawcze może również zmieniać się na różne sposoby, wciąż będąc ograniczonym. Jeśli środowisko wykonawcze jest proporcjonalne do (n mod 5) + 1, jest nadal O(1), ale ujawnia informacje o n. Dlatego bardziej preferowany może być bardziej złożony algorytm z płynniejszym czasem działania, nawet jeśli może być asymptotycznie (a być może nawet w praktyce) wolniejszy.
Christian Semrau,
Właśnie dlatego bcrypt jest uważany za dobry; spowalnia wszystko
David mówi Przywróć Monikę
@DavidGrinberg To jest powód, dla którego używa się bcrypt i pasuje do pytania. Nie ma to jednak związku z tą odpowiedzią, która mówi o atakach w czasie.
Christian Semrau,
37

Alistra przybrała go, ale nie podała żadnych przykładów, więc to zrobię.

Masz listę 10 000 kodów UPC dla tego, co sprzedaje Twój sklep. 10 cyfr UPC, liczba całkowita w cenie (cena w centach) i 30 znaków opisu dla paragonu.

Podejście O (log N): masz posortowaną listę. 44 bajty, jeśli ASCII, 84 jeśli Unicode. Alternatywnie, potraktuj UPC jako int64, a otrzymasz 42 i 72 bajty. 10 000 rekordów - w najwyższym przypadku patrzysz na nieco mniej niż megabajt pamięci.

Podejście O (1): Nie przechowuj UPC, zamiast tego używasz go jako wpisu do tablicy. W najniższym przypadku patrzysz na prawie jedną trzecią terabajta pamięci.

To, które podejście zastosujesz, zależy od twojego sprzętu. W większości rozsądnych nowoczesnych konfiguracji będziesz używać metody log N. Mogę sobie wyobrazić, że drugie podejście jest właściwą odpowiedzią, jeśli z jakiegoś powodu działasz w środowisku, w którym pamięć RAM jest krytycznie krótka, ale masz dużo pamięci masowej. Jedna trzecia terabajta na dysku to nie wielka sprawa, warto dostać swoje dane do jednej sondy dysku. Proste podejście binarne zajmuje średnio 13. (Zauważ jednak, że klastrowanie kluczy pozwala sprowadzić to do gwarantowanych 3 odczytów, a w praktyce buforujesz pierwszy).

Loren Pechtel
źródło
2
Jestem trochę zdezorientowany. Czy mówisz o utworzeniu tablicy o wartości 10 miliardów wpisów (z których większość będzie niezdefiniowana) i traktowaniu UPC jako indeksu w tej tablicy?
David Z
7
@DavidZ Tak. Jeśli użyjesz rzadkiej tablicy, możesz nie uzyskać O (1), ale zajmie ona tylko 1 MB pamięci. Jeśli użyjesz rzeczywistej tablicy, masz gwarancję dostępu O (1), ale zajmie ona pamięć 1/3 TB.
Navin,
W nowoczesnym systemie zajmie 1/3 TB przestrzeni adresowej, ale to nie znaczy, że zbliży się do tak dużej ilości przydzielonej pamięci zapasowej. Większość współczesnych systemów operacyjnych nie zatwierdza pamięci dla przydziałów, dopóki nie będzie to konieczne. Robiąc to, zasadniczo ukrywasz asocjacyjną strukturę wyszukiwania danych w systemie wirtualnej pamięci OS / sprzęt.
Phil Miller,
@Novelocrat Prawda, ale jeśli robisz to z szybkością pamięci RAM, czas wyszukiwania nie będzie miał znaczenia, nie ma powodu, aby używać 40 MB zamiast 1 MB. Wersja macierzowa ma sens tylko wtedy, gdy dostęp do pamięci jest drogi - idziesz na dysk.
Loren Pechtel,
1
Lub gdy nie jest to operacja krytyczna pod względem wydajności, a czas programisty jest kosztowny - mówienie malloc(search_space_size)i zapisywanie do tego, co zwraca, jest tak proste, jak to tylko możliwe.
Phil Miller,
36

Rozważ czerwono-czarne drzewo. Ma dostęp, wyszukiwanie, wstawianie i usuwanie O(log n). Porównaj z tablicą, która ma dostęp, O(1)a reszta operacji to O(n).

Więc biorąc pod uwagę aplikację, w której wstawiamy, usuwamy lub wyszukujemy częściej niż mamy dostęp i wybór pomiędzy tylko tymi dwiema strukturami, wolelibyśmy czerwono-czarne drzewo. W takim przypadku możesz powiedzieć, że wolimy bardziej kłopotliwy O(log n)czas dostępu do drzewa czerwono-czarnego .

Czemu? Ponieważ dostęp nie jest naszym nadrzędnym celem. Dokonujemy kompromisu: na wydajność naszej aplikacji wpływają inne czynniki niż ten. Umożliwiamy temu konkretnemu algorytmowi obniżenie wydajności, ponieważ osiągamy duże zyski dzięki optymalizacji innych algorytmów.

Odpowiedź na twoje pytanie jest więc następująca: gdy tempo wzrostu algorytmu nie jest tym, co chcemy zoptymalizować , kiedy chcemy zoptymalizować coś innego. Wszystkie pozostałe odpowiedzi są szczególnymi przypadkami tego. Czasami optymalizujemy czas wykonywania innych operacji. Czasami optymalizujemy pamięć. Czasami optymalizujemy pod kątem bezpieczeństwa. Czasami optymalizujemy łatwość konserwacji. Czasami optymalizujemy czas rozwoju. Nawet nadrzędna stała na tyle niska, że ​​materia optymalizuje się pod kątem czasu działania, gdy wiadomo, że szybkość wzrostu algorytmu nie ma największego wpływu na czas działania. (Jeśli Twój zestaw danych znajdował się poza tym zakresem, zoptymalizowałbyś tempo wzrostu algorytmu, ponieważ ostatecznie zdominowałoby stałą.) Wszystko ma swój koszt, aw wielu przypadkach sprzedajemy koszt wyższego tempa wzrostu dla algorytm do optymalizacji czegoś innego.

jpmc26
źródło
Nie jestem pewien, w jaki sposób operacje, które pozwalają na użycie tablicy z wyszukiwaniem O (1) i aktualizacjami O (n), odpowiadają czerwono-czarnemu drzewu, o czym ludzie myśleli (przynajmniej ja). Przez większość czasu najpierw myślałam o wyszukiwaniu opartym na kluczach drzewa czerwono-czarnego. Ale aby dopasować się do tablicy, powinna być nieco inna struktura, która utrzymuje liczbę podwęzłów w górnych węzłach, aby zapewnić wyszukiwanie oparte na indeksie i ponowne indeksowanie po wstawieniu. Chociaż zgadzam się, że czerwono-czarna może być używana do utrzymania równowagi, możesz użyć zbalansowanego drzewa, jeśli chcesz być niejasny co do szczegółów odpowiednich operacji.
ony
@ony Czerwono-czarne drzewo może być użyte do zdefiniowania struktury typu mapy / słownika, ale nie musi tak być. Węzły mogą być po prostu elementami, zasadniczo implementującymi posortowaną listę.
jpmc26,
posortowana lista i tablica określająca kolejność elementów mają różną ilość informacji. Jeden opiera się na kolejności między elementami i zestawem, a drugi określa dowolną sekwencję, która nie jest konieczna, określa kolejność między elementami. Inną sprawą jest „dostęp” i „wyszukiwanie”, które deklarujesz jako O(log n)„czerwono-czarne drzewo”? Wstawienie 5w pozycji 2 tablicy [1, 2, 1, 4]spowoduje [1, 2, 5, 1 4](element 4zostanie zaktualizowany indeks z 3 do 4). Jak dostaniesz to zachowanie w O(log n)„czerwono-czarnym drzewie”, które określasz jako „posortowaną listę”?
ony
@ony "posortowana lista i tablica określająca kolejność elementów mają różną ilość informacji." Tak, i jest to część tego, dlaczego mają różne cechy wydajności. Nie rozumiesz sedna sprawy. Jedno nie jest spadkiem zastępowania drugiego we wszystkich sytuacjach. Oni optymalizować różne rzeczy i dokonać różnych kompromisów , a chodzi o to, że deweloperzy są podejmowania decyzji dotyczących tych kompromisów stale.
jpmc26
@ony Dostęp, wyszukiwanie, wstawianie i usuwanie mają określone znaczenie w kontekście wydajności algorytmu. Access pobiera element według pozycji. Wyszukiwanie polega na zlokalizowaniu elementu według wartości (która ma jedynie praktyczne zastosowanie jako kontrola ograniczania struktury niemapowej). Wstawianie i usuwanie powinno być jednak proste. Przykładowe użycie można zobaczyć tutaj .
jpmc26
23

Tak.

W prawdziwym przypadku przeprowadziliśmy kilka testów dotyczących wyszukiwania tabel przy użyciu zarówno krótkich, jak i długich kluczy łańcuchowych.

Zastosowaliśmy a std::map, std::unordered_mapz hashem, który próbkuje maksymalnie 10 razy na całej długości łańcucha (nasze klucze wydają się być jak guid, więc to jest przyzwoite), i hash, który pobiera próbki z każdej postaci (teoretycznie zmniejsza kolizje), niesortowany wektor, w którym dokonujemy ==porównania, i (jeśli dobrze pamiętam) niesortowany wektor, w którym również przechowujemy skrót, najpierw porównaj skrót, a następnie porównaj znaki.

Algorytmy te wahają się od O(1)(mapa_uporządkowana) do O(n)(wyszukiwanie liniowe).

W przypadku skromnego rozmiaru N dość często O (n) pokonuje O (1). Podejrzewamy, że dzieje się tak, ponieważ kontenery oparte na węzłach wymagały od naszego komputera częstszego przeskakiwania w pamięci, podczas gdy kontenery oparte na liniach nie.

O(lg n)istnieje między nimi. Nie pamiętam, jak to się stało.

Różnica w wydajności nie była tak duża, a przy większych zestawach danych zestaw oparty na haszowaniu działał znacznie lepiej. Więc utknęliśmy z nieuporządkowaną mapą opartą na haszowaniu.

W praktyce dla rozsądnego rozmiaru n O(lg n)jest O(1). Jeśli twój komputer ma tylko miejsce na 4 miliardy wpisów w tabeli, to O(lg n)jest ograniczony przez 32. (lg (2 ^ 32) = 32) (w informatyce lg to skrót od log 2).

W praktyce algorytmy lg (n) są wolniejsze niż algorytmy O (1) nie z powodu logarytmicznego współczynnika wzrostu, ale dlatego, że część lg (n) zwykle oznacza, że ​​algorytm ma pewien poziom złożoności, a złożoność ta dodaje większy stały współczynnik niż jakikolwiek z „wzrostów” z wyrażenia lg (n).

Jednak złożone algorytmy O (1) (takie jak mapowanie skrótów) mogą łatwo mieć podobny lub większy stały współczynnik.

Jak - Adam Nevraumont
źródło
21

Możliwość równoległego wykonywania algorytmu.

Nie wiem, czy istnieje przykład dla klas O(log n)i O(1), ale w przypadku niektórych problemów wybierasz algorytm o wyższej klasie złożoności, gdy algorytm jest łatwiejszy do wykonania równolegle.

Niektóre algorytmy nie mogą być zrównoleglone, ale mają tak niską klasę złożoności. Rozważ inny algorytm, który osiąga ten sam wynik i może być łatwo zrównoleglony, ale ma wyższą klasę złożoności. Podczas wykonywania na jednym komputerze drugi algorytm jest wolniejszy, ale podczas wykonywania na wielu komputerach rzeczywisty czas wykonywania jest coraz krótszy, podczas gdy pierwszy algorytm nie może przyspieszyć.

Płyn symulujący
źródło
Ale wszystko, co robi paralelizacja, to redukowanie stałego czynnika, o którym mówili inni, prawda?
gengkev
1
Tak, ale algorytm równoległy może podzielić współczynnik stały przez 2 za każdym razem, gdy podwoisz liczbę wykonujących się maszyn. Kolejny algorytm jednowątkowy może zredukować stały współczynnik tylko jeden raz w stały sposób. Dzięki algorytmowi równoległemu możesz dynamicznie reagować na wielkość n i być szybszym w czasie wykonywania zegara ściennego.
Simulant
15

Załóżmy, że wdrażasz czarną listę w systemie osadzonym, na której mogą znajdować się numery od 0 do 1 000 000. To pozostawia dwie możliwe opcje:

  1. Użyj zestawu bitów 1 000 000 bitów
  2. Użyj posortowanej tablicy liczb całkowitych z czarnej listy i użyj wyszukiwania binarnego, aby uzyskać do nich dostęp

Dostęp do zestawu bitów będzie gwarantowany stały dostęp. Pod względem złożoności czasowej jest optymalna. Zarówno z teoretycznego, jak i praktycznego punktu widzenia (jest to O (1) z wyjątkowo niskim stałym narzutem).

Mimo to możesz preferować drugie rozwiązanie. Zwłaszcza jeśli spodziewasz się, że liczba liczb całkowitych z czarnej listy będzie bardzo mała, ponieważ zwiększy to wydajność pamięci.

I nawet jeśli nie opracowujesz systemu wbudowanego, w którym brakuje pamięci, mogę po prostu zwiększyć arbitralny limit od 1 000 000 do 1 000 000 000 000 i przedstawić ten sam argument. Wtedy zestaw bitów wymagałby około 125 GB pamięci. Gwarantowana w najgorszym przypadku złożoność O (1) może nie przekonać twojego szefa do zapewnienia ci tak potężnego serwera.

Tutaj zdecydowanie wolałbym wyszukiwanie binarne (O (log n)) lub drzewo binarne (O (log n)) niż zestaw bitów O (1). I prawdopodobnie tablica skrótu o najgorszej złożoności O (n) pobije je wszystkie w praktyce.

Philipp Claßen
źródło
12

Ludzie już odpowiedzieli na twoje dokładne pytanie, więc odpowiem na nieco inne pytanie, o którym ludzie mogą pomyśleć, kiedy tu przybędą.

Wiele algorytmów i struktur danych „O (1)” faktycznie zajmuje tylko oczekiwany czas O (1), co oznacza, że ​​ich średni czas działania wynosi O (1), prawdopodobnie tylko pod pewnymi założeniami.

Typowe przykłady: tablice skrótów, rozszerzanie „list tablic” (inaczej tablic / wektorów o dynamicznym rozmiarze).

W takich scenariuszach możesz preferować stosowanie struktur danych lub algorytmów, których czas gwarantuje, że czas będzie absolutnie ograniczony logarytmicznie, mimo że mogą one działać średnio gorzej.
Przykładem może być zatem zrównoważone drzewo wyszukiwania binarnego, którego czas działania jest średnio gorszy, ale w najgorszym przypadku lepszy.

użytkownik541686
źródło
11

Bardziej ogólne pytanie, czy istnieją sytuacje, w których można by wolą O(f(n))algorytm do O(g(n))algorytmu, chociaż g(n) << f(n)jak ndąży do nieskończoności. Jak już wspomniano inni, odpowiedź jest jednoznaczna „tak” w przypadku, gdy f(n) = log(n)i g(n) = 1. Czasami tak jest, nawet w przypadku f(n)wielomianu, ale g(n)wykładnika. Znanym i ważnym przykładem jest algorytm Simplex do rozwiązywania problemów programowania liniowego. W latach 70. wykazano, że tak jest O(2^n). Dlatego jego zachowanie w najgorszym przypadku jest niemożliwe. Ale - jego średnie zachowanie w przypadku jest wyjątkowo dobre, nawet w przypadku problemów praktycznych z dziesiątkami tysięcy zmiennych i ograniczeń. W latach 80. wielomianowe algorytmy czasowe (npAlgorytm punktu wewnętrznego Karmarkara ) do programowania liniowego został odkryty, ale 30 lat później algorytm simpleks nadal wydaje się algorytmem z wyboru (z wyjątkiem niektórych bardzo dużych problemów). Wynika to z oczywistego powodu, że zachowanie średnich przypadków jest często ważniejsze niż zachowanie gorszych przypadków, ale także z bardziej subtelnego powodu, że algorytm simpleks jest w pewnym sensie bardziej pouczający (np. Łatwiej jest wydobyć informacje o wrażliwości).

John Coleman
źródło
10

Aby włożyć moje 2 centy:

Czasami algorytm gorszej złożoności jest wybierany zamiast lepszego, gdy algorytm działa w określonym środowisku sprzętowym. Załóżmy, że nasz algorytm O (1) niesekwencyjnie uzyskuje dostęp do każdego elementu bardzo dużej tablicy o stałej wielkości, aby rozwiązać nasz problem. Następnie umieść ten układ na mechanicznym dysku twardym lub taśmie magnetycznej.

W takim przypadku algorytm O (logn) (załóżmy, że uzyskuje sekwencyjny dostęp do dysku) staje się bardziej korzystny.

uylmz
źródło
Mógłbym dodać tutaj, że na napędzie lub taśmie sekwencyjnego dostępu algorytm O (1) zamienia się w O (n), dlatego rozwiązanie sekwencyjne staje się bardziej korzystne. Wiele operacji O (1) zależy od dodawania i indeksowania wyszukiwania będącego algorytmem o stałym czasie, którego nie ma w przestrzeni dostępu sekwencyjnego.
TheHansinator,
9

Istnieje dobry przypadek użycia algorytmu O (log (n)) zamiast algorytmu O (1), który zignorowano w wielu innych odpowiedziach: niezmienność. Mapy haszowania mają wartości O (1), które przyjmują i pobierają, przy założeniu dobrego rozkładu wartości skrótu, ale wymagają stanu zmiennego. Niezmienne mapy drzew mają O (log (n)) umieszcza i pobiera, co jest asymptotycznie wolniejsze. Jednak niezmienność może być na tyle cenna, aby zrekompensować gorszą wydajność, aw przypadku, gdy trzeba zachować wiele wersji mapy, niezmienność pozwala uniknąć konieczności kopiowania mapy, która jest O (n), i dlatego może się poprawić występ.

Przywróć Monikę
źródło
9

Po prostu: Ponieważ współczynnik - koszty związane z konfiguracją, przechowywaniem i czasem wykonania tego kroku - może być znacznie, znacznie większy w przypadku mniejszego problemu dużego-O niż większego. Big-O jest tylko miarą skalowalności algorytmów .

Rozważ następujący przykład ze słownika hakera, proponując algorytm sortowania oparty na interpretacji mechaniki kwantowej w wielu światach :

  1. Zezwól losowo na tablicę za pomocą procesu kwantowego,
  2. Jeśli tablica nie jest posortowana, zniszcz wszechświat.
  3. Wszystkie pozostałe wszechświaty są teraz posortowane [włączając ten, w którym jesteś].

(Źródło: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Zauważ, że big-O tego algorytmu jest O(n), który bije jakikolwiek znany algorytm sortowania do tej pory na elementach ogólnych. Współczynnik kroku liniowego jest również bardzo niski (ponieważ jest to tylko porównanie, a nie zamiana, która odbywa się liniowo). Podobny algorytm można w rzeczywistości zastosować do rozwiązania dowolnego problemu zarówno w NP, jak i co-NP w czasie wielomianowym, ponieważ każde możliwe rozwiązanie (lub możliwy dowód braku rozwiązania) można wygenerować za pomocą procesu kwantowego, a następnie zweryfikować w czas wielomianowy.

Jednak w większości przypadków prawdopodobnie nie chcemy ryzykować, że wiele światów może być niepoprawnych, nie wspominając już o tym, że realizacja kroku 2 jest nadal „pozostawiana jako ćwiczenie dla czytelnika”.

TheHansinator
źródło
7

W dowolnym momencie, gdy n jest ograniczone, a stały mnożnik algorytmu O (1) jest wyższy niż granica log (n). Na przykład przechowywanie wartości w haszcie to O (1), ale może wymagać kosztownego obliczenia funkcji skrótu. Jeśli elementy danych można w prosty sposób porównać (w odniesieniu do pewnej kolejności), a ograniczenie na n jest takie, że log n jest znacznie mniejszy niż obliczenia skrótu dla dowolnego jednego elementu, wówczas przechowywanie w zrównoważonym drzewie binarnym może być szybsze niż przechowywanie w hashset.

Dmitrij Rubanowicz
źródło
6

W sytuacji, w której potrzebujesz mocnej górnej granicy, wybrałbyś np. Heapsort w przeciwieństwie do Quicksort, ponieważ średnie zachowanie heapsortu jest również jego najgorszym przypadkiem.

Markiz Lorne
źródło
6

Dodanie do już dobrych odpowiedzi. Praktycznym przykładem mogą być indeksy Hash vs. indeksy B-drzewa w bazie danych Postgres.

Indeksy skrótów tworzą indeks tabeli skrótów, aby uzyskać dostęp do danych na dysku, podczas gdy btree, jak sama nazwa wskazuje, używa struktury danych Btree.

W czasie Big-O są to O (1) vs O (logN).

Indeksy hash są obecnie odradzane w postgresie, ponieważ w rzeczywistej sytuacji, szczególnie w systemach baz danych, uzyskanie haszowania bez kolizji jest bardzo trudne (może prowadzić do najgorszej złożoności O (N)) iz tego powodu jeszcze trudniej jest zrobić są odporne na awarie (tzw. zapis z wyprzedzeniem - WAL w postgresie).

Taki kompromis występuje w tej sytuacji, ponieważ O (logN) jest wystarczająco dobre dla indeksów, a implementacja O (1) jest dość trudna, a różnica czasu nie miałaby tak naprawdę znaczenia.

Madusudanan
źródło
4

Kiedy njest mały i O(1)ciągle powolny.

HoboBen
źródło
3
  1. Gdy jednostka robocza „1” w O (1) jest bardzo wysoka w stosunku do jednostki roboczej w O (log n), a oczekiwany rozmiar zestawu jest niewielki. Na przykład, prawdopodobnie wolniej jest obliczać kody skrótu słownika niż iterować tablicę, jeśli są tylko dwa lub trzy elementy.

lub

  1. Gdy pamięć lub inne wymagania dotyczące zasobów innych niż czasowe w algorytmie O (1) są wyjątkowo duże w stosunku do algorytmu O (log n).
Joel Coehoorn
źródło
3
  1. podczas przeprojektowywania programu okazuje się, że procedura jest zoptymalizowana za pomocą O (1) zamiast O (lgN), ale jeśli nie jest to wąskie gardło tego programu i trudno jest zrozumieć algę O (1). Wtedy nie musiałbyś używać algorytmu O (1)
  2. gdy O (1) potrzebuje dużo pamięci, której nie można dostarczyć, a czas O (lgN) może zostać zaakceptowany.
yanghaogn
źródło
1

Często dzieje się tak w przypadku aplikacji bezpieczeństwa, w których chcemy projektować problemy, których algorytmy są celowo powolne, aby uniemożliwić komuś zbyt szybkie uzyskanie odpowiedzi na problem.

Oto kilka przykładów z mojej głowy.

  • Mieszanie haseł jest czasami spowolnione arbitralnie, aby utrudnić odgadnięcie haseł za pomocą brutalnej siły. Ten post dotyczący bezpieczeństwa informacji zawiera punktor na ten temat (i wiele więcej).
  • Bit Coin wykorzystuje kontrolowany powolny problem, który sieć komputerów rozwiązuje, aby „wydobywać” monety. Umożliwia to wydobywanie waluty według kontrolowanego kursu przez system zbiorowy.
  • Szyfry asymetryczne (takie jak RSA ) zostały zaprojektowane do celowego odszyfrowywania bez użycia kluczy, aby zapobiec złamaniu szyfrowania przez osobę inną niż klucz prywatny. Algorytmy są przeznaczone do pęknięty w miejmy nadzieję O(2^n)czasie, gdy njest bitową długość klucza (to brute force).

Gdzie indziej w CS, szybkie sortowanie jest O(n^2)w najgorszym przypadku, ale w ogólnym przypadku jest O(n*log(n)). Z tego powodu analiza „Big O” czasami nie jest jedyną rzeczą, na której zależy Ci analizowanie wydajności algorytmu.

Frank Bryce
źródło