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?
algorithm
big-o
time-complexity
V.Leymarie
źródło
źródło
O(log n)
algorytm odO(1)
algorytmu, jeśli rozumiem ten pierwszy, ale nie ten drugi ...Odpowiedzi:
Może być wiele powodów, aby preferować algorytm o większej złożoności czasu O niż niższy:
10^5
jest lepszy z punktu widzenia big-O niż1/10^5 * log(n)
(O(1)
vsO(log(n)
), ale dla najbardziej uzasadnionegon
pierwszy będzie działał lepiej. Na przykład najlepsza złożoność mnożenia macierzy jestO(n^2.373)
taka, że stała jest tak wysoka, że (o ile mi wiadomo) biblioteki obliczeniowe jej nie wykorzystują.O(n*log(n))
lubO(n^2)
algorytm.O(log log N)
złożoność czasową znalezienia elementu, ale istnieje również drzewo binarne, które znajduje to samoO(log n)
. Nawet w przypadku ogromnych liczbn = 10^20
różnica jest znikoma.O(n^2)
i wymagaO(n^2)
pamięci. Może być preferowane wO(n^3)
czasie iO(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 algorytmemw 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ć)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.źródło
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.
źródło
lg n
jest tak bardzo zbliżony dok
dużego,n
że większość operacji nigdy nie zauważy różnicy.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.
źródło
O(logn)
więcejO(1)
. Można bardzo łatwo wyobrazić sobie sytuację, w której dla wszystkich możliwychn
zastosowań aplikacja działająca w mniejszej ilości pamięci działałaby szybciej, nawet przy większej złożoności.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 .
źródło
(n mod 5) + 1
, jest nadalO(1)
, ale ujawnia informacje on
. 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.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).
źródło
malloc(search_space_size)
i zapisywanie do tego, co zwraca, jest tak proste, jak to tylko możliwe.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 toO(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.
źródło
O(log n)
„czerwono-czarne drzewo”? Wstawienie5
w pozycji 2 tablicy[1, 2, 1, 4]
spowoduje[1, 2, 5, 1 4]
(element4
zostanie zaktualizowany indeks z 3 do 4). Jak dostaniesz to zachowanie wO(log n)
„czerwono-czarnym drzewie”, które określasz jako „posortowaną listę”?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_map
z 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) doO(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)
jestO(1)
. Jeśli twój komputer ma tylko miejsce na 4 miliardy wpisów w tabeli, toO(lg n)
jest ograniczony przez32
. (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.
źródło
Możliwość równoległego wykonywania algorytmu.
Nie wiem, czy istnieje przykład dla klas
O(log n)
iO(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ć.
źródło
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:
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.
źródło
Moja odpowiedź tutaj Szybka losowa selekcja ważona we wszystkich wierszach macierzy stochastycznej jest przykładem, w którym algorytm o złożoności O (m) jest szybszy niż algorytm o złożoności O (log (m)), kiedy
m
nie jest zbyt duży.źródło
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.
źródło
Bardziej ogólne pytanie, czy istnieją sytuacje, w których można by wolą
O(f(n))
algorytm doO(g(n))
algorytmu, chociażg(n) << f(n)
jakn
dąży do nieskończoności. Jak już wspomniano inni, odpowiedź jest jednoznaczna „tak” w przypadku, gdyf(n) = log(n)
ig(n) = 1
. Czasami tak jest, nawet w przypadkuf(n)
wielomianu, aleg(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 jestO(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).źródło
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.
źródło
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.
źródło
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 :
(Ź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”.
źródło
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.
źródło
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.
źródło
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.
źródło
Kiedy
n
jest mały iO(1)
ciągle powolny.źródło
lub
źródło
źródło
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.
O(2^n)
czasie, gdyn
jest 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 jestO(n*log(n))
. Z tego powodu analiza „Big O” czasami nie jest jedyną rzeczą, na której zależy Ci analizowanie wydajności algorytmu.źródło