Przykład algorytmu, w którym element wykonawczy niskiego rzędu dominuje w środowisku wykonawczym dla jakichkolwiek praktycznych danych wejściowych?

Notacja Big-O ukrywa stałe współczynniki, więc istnieją pewne algorytmy $O(n)$ , które są niewykonalne dla jakiegokolwiek rozsądnego rozmiaru wejściowego, ponieważ współczynnik na jest tak duży.$n$

Czy są jakieś znane algorytmy, których środowisko wykonawcze to ale z jakimś niskim terminem, który jest tak ogromny, że dla rozsądnych wielkości wejściowych całkowicie dominuje w środowisku wykonawczym? Chciałbym użyć takiego algorytmu jako przykładu w kursie algorytmów, ponieważ daje to dobry powód, dla którego notacja wielkiej litery O nie jest niczym.$O(f(n))$$o(f(n))$

Dzięki!

Kryptografia jest przykładem, jeśli jest zdegenerowana. Na przykład zerwanie z szyfrowaniem AES to - wystarczy znaleźć odpowiedni klucz spośród skończonej liczby, 2 128 lub 2 192 lub 2 256 w zależności od wielkości klucza (zakładając, że znana jest wystarczająca ilość tekstu jawnego ustalić klucz jednoznacznie). Jednak nawet 2 128 operacji zajęłoby dziś wszystkie komputery (miliard lub więcej, z których każdy wykonuje około miliarda operacji na sekundę) więcej niż czas życia wszechświata (około miliarda miliardów sekund).$O(1)$$2^{128}$$2^{192}$$2^{256}$$2^{128}$

Nieco innym sposobem zilustrowania, dlaczego big-O to nie wszystko, jest zauważenie, że czasami używamy innego algorytmu dla małych rozmiarów danych wejściowych. Na przykład weź Quicksort. Przy odpowiednim wyborze elementu przestawnego (co jest trudną sprawą!), Jest to . Quicksort działa na zasadzie „dziel i rządź”: każda instancja wymaga wykonania wielu sortowań małych tablic. W przypadku małych tablic metody kwadratowe, takie jak sortowanie wstawiane, działają lepiej. Aby uzyskać najlepszą wydajność, szybkie sortowanie dużej tablicy obejmuje wiele serii sortowania w przypadku małych rozmiarów.$O(n \lg n)$

Przychodzą mi na myśl dwa przykłady z zakresu sparametryzowanej złożoności i algorytmów FPT. To może nie być dokładnie to, czego szukasz, ale proszę bardzo.

Zastanów się nad problemem graficznym, takim jak 3-COLORING lub HAM-CYCLE. Oba problemy mogą być wyrażone w monadycznej logice drugiego rzędu, a zatem można je rozstrzygać w liniowym czasie wykresów z ograniczoną szerokością. Jest to wynik Bruno Courcelle , ale wynikowy algorytm jest daleki od praktycznego.

Drugi przykład to głęboki wynik Lenstry, mówiąc, że całkowite programy liniowe (ILP) o stałej liczbie zmiennych można rozwiązać w czasie liniowym. Dzięki dodatkowej pracy wykonanej przez Ravi Kannana mamy problem, że problem wykonalności programowania liczb całkowitych można rozwiązać za pomocą operacji arytmetycznych na liczbach całkowitych o rozmiarze O ( p 2 p L ) , gdzie p jest liczbą zmiennych ILP, a L jest liczbą bitów na wejściu. To znowu powoduje powstanie algorytmów FPT, które są praktyczne tylko w bardzo małych przypadkach.$O(p^{9p/2})L$$O(p^{2p}L)$$p$$L$

nieco związane z twoim pytaniem są algorytmy, o których wiadomo, że teoretycznie mają dobrą wydajność, ale nie są używane w rzeczywistych problemach z powodu niepraktyczności w mniejszych przypadkach. innymi słowy, tak jak prosisz, „wydajność reklamowana” jest możliwa tylko w przypadku dużych nakładów teoretycznych, nie widzianych w praktycznych zastosowaniach. czasami znajduje to odzwierciedlenie w szacunkach Big-Oh, innym razem nie do końca. niektóre algorytmy mają dobrą teoretyczną „wydajność”, ale są bardzo logicznie złożone i nigdy nie zostały wdrożone przez nikogo, dlatego też „wydajność” w praktycznych rozmiarach instancji nie jest nawet znana, np. jak w przypadku problemu maksymalnego przepływu .

• testowanie pierwotności w P za pomocą algorytmu AKS

• Algorytm mnożenia macierzy Coppersmitha-winograda

• patrz także, czy najnowocześniejsze algorytmy maksymalnego przepływu są praktyczne? tcs.se

• zobacz także potężne algorytmy zbyt złożone, aby zaimplementować tcs.se

• algorytmy galaktyczne Blog RJLipton

To trochę żart, ale ma poważną stronę ...

$O(n\log n)$$O(n^2)$