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

10

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!

algorithms asymptotics

— templatetypedef
źródło

Algorytmy, które najpierw konfigurują dużą tabelę, a następnie wykonują szybkie wyszukiwania w tabeli dla każdego elementu wejściowego? Jeśli stół jest wystarczająco duży, liczba elementów musi być ogromna, aby zrównoważyć koszty utworzenia stołu. Wyszukiwarki są jednym z przykładów, jeśli jest liczbą zapytań.

n

$n$

— András Salamon,

Słyszałem, że programowanie liniowe jest takie. Simplex jest wykładniczy, ale szybszy niż algorytmy wielomianowe w praktyce.

— jmite

1

Nie znam żadnego algorytmu, który pasowałby do twoich potrzeb, ale szukałbym czegoś, co miałoby co najwyżej liniowy czas działania, ponieważ poza tym bardzo wątpiłbym, że mniejsze terminy mogłyby zdominować wiodący termin dla najbardziej rozsądnych danych wejściowych. Ale może k-way scalesort odpowiada Twoim potrzebom, gdy jest używany do sortowania dużych zbiorów danych? Problem polega na zminimalizowaniu dostępu do pamięci dodatkowej, ponieważ kosztują one dużo czasu - choć nie jestem całkowicie pewien, czy byłby to odpowiedni przykład dla tego, co chcesz zademonstrować, i nie wydaje mi się, aby było to wystarczająco proste ilustrować.

— G. Bach,

nieco podobny do potężnych algorytmów zbyt skomplikowanych do wdrożenia , patrz także blog rjlipton na temat algorytmów galaktycznych

— vn

2

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, lub lub zależności od wielkości klucza (zakładając, że znana jest wystarczająca ilość tekstu jawnego ustalić klucz jednoznacznie). Jednak nawet 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)$

— Gilles „SO- przestań być zły”
źródło

Nie sądzę, że łamanie szyfrowania jest tutaj rozsądnym przykładem; jedną rzeczą jest to, że aby przeanalizować problem znalezienia prawidłowego klucza w sposób asymptotyczny, musielibyśmy wziąć pod uwagę teoretycznie dostępne wersje Rijndael z niestałym rozmiarem klucza, tj. złamanie klucza dla kluczy o rozmiarze

. W przeciwnym razie równie dobrze moglibyśmy powiedzieć, że każdy algorytm, który kończy działanie, działa w

dla wejścia o ustalonym rozmiarze.

n

$n$

O (1)

$\mathcal{O}(1)$

— G. Bach,

@ G.Bach Istotą tego przykładu jest to, że jest to niewykonalne (którą teorię złożoności wiąże z wysoką złożonością), mimo że jest to czas stały (pod względem wielkości tekstu zaszyfrowanego).

— Gilles „SO- przestań być zły”

2

Nie sądzę, żeby twój pierwszy przykład działał. Ponieważ istnieje tylko wiele opcji do sprawdzenia, środowisko uruchomieniowe algorytmu to

, więc nie ma niskiego rzędu terminu

który odpowiada za cały środowisko wykonawcze.

O (1)

$O(1)$

o (1)

$o(1)$

— templatetypedef

1

@templatetypedef Przerwanie szyfrowania wiadomości zaszyfrowanej przez AES to

pod względem długości wiadomości .

O (1)

$O(1)$

— Gilles „SO- przestań być zły”

1

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 , gdzie jest liczbą zmiennych ILP, a 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$

— Juho
źródło

2

O (n)

$O(n)$

o (n)

$o(n)$

0

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

— vzn
źródło

Ale czy są one niepraktyczne, ponieważ dominują warunki niskiego rzędu lub ponieważ stałe w terminach wyższych rzędów są złe?

— David Richerby,

albo albo kombinacja, trudno byłoby wyodrębnić w każdym przypadku. skutecznie / praktycznie to ten sam efekt.

— vzn

-1

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

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

— David Richerby
źródło

1

Nie, to jest inne. Quicksort jest przydatny w praktyce, ponieważ nie ma kwadratowego terminu na typowe dane wejściowe, bez względu na to, jak duży jest rozmiar. Jeśli wybór osi przestawnej jest zły dla układu danych, Quicksort wykazuje zachowanie kwadratowe nawet przy niewielkich wejściach.

— Gilles „SO- przestań być zły”