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

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?

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.

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.

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 ² <6 n ² ) . 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.

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 .

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

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.

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.

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

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.

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 mnie jest zbyt duży.

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.

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

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.

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.

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

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.

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.

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.

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

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

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

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.

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.