Jakie są problemy, gdy wiemy, że mamy optymalny algorytm?

Jakie są nietrywialne problemy, o których wiemy, że obecny algorytm jest asymptotycznie optymalny? (Do maszyn Turinga)

Jak to udowodniono?

Każdy algorytm, który wymaga czasu liniowego i musi odczytać całe dane wejściowe, musi być optymalny asymptotycznie. Podobnie, jak komentuje Raphael, optymalny jest każdy algorytm, którego środowisko wykonawcze jest tego samego rzędu co wielkość wyjściowa.

Jeśli rozważaną miarą złożoności jest złożoność zapytań, tzn. Ile razy maszyna musi spojrzeć na dane wejściowe w celu rozwiązania konkretnego problemu, istnieje wiele problemów, dla których mamy optymalne algorytmy. Powodem tego jest to, że dolne granice złożoności zapytań są łatwiejsze do osiągnięcia niż dolne granice złożoności czasowej lub przestrzennej, dzięki niektórym popularnym technikom, w tym metodzie przeciwnika .

Minusem jest jednak to, że ta miara złożoności jest prawie wyjątkowo wykorzystywana w przetwarzaniu informacji kwantowej, ponieważ zapewnia łatwy sposób wykazania luki między kwantową a klasyczną mocą obliczeniową. Najbardziej znanym algorytmem kwantowym w tym układzie jest algorytm Grovera . Biorąc pod uwagę ciąg binarny dla którego istnieje pojedyncze i takie, że x i = n , musisz znaleźć i . Klasycznie (bez komputera kwantowego) najbardziej trywialny algorytm jest optymalny: musisz znaleźć ten ciąg średnio n / 2 razy, aby znaleźć$x_1,\dots ,x_n$$i$$x_i=n$$i$$n/2$ . Grover podał algorytm kwantowy, który robi to w O ( $i$zapytania do ciągu. Zostało to również udowodnione jako optymalne.$O(\sqrt n)$

• Jeśli chcesz zmienić swój model, istnieje kilka dolnych granic w strukturach danych. Zobacz Dolne granice dla struktur danych dla wskaźników do dobrych odniesień dla dolnych granic w strukturach danych.
• Na podstawie związanego z sortowaniem w modelu porównawczym, o którym wspomnieli tutaj niektórzy ludzie, można uzyskać podobne ograniczenie dla problemu wypukłego kadłuba, rozważając przypadek, w którym dane wejściowe składają się z punktów wzdłuż wykresu rosnąca funkcja w pierwszej ćwiartce samolotu.$\Omega(n log n)$

1. Sortowanie porównawcze przy użyciu porównań (sortowanie scalające, aby wymienić jedno) jest optymalne, dowód polega na obliczeniu wysokości drzewa za pomocą n ! pozostawia.$O (n \log n)$$n!$

2. Zakładając, że Unique Games Conjecture, Khot, Kindler, Mossel i O'donnell pokazali, że NP-zupełne jest przybliżenie Max-Cut lepiej niż algorytm Goemansa i Williamsona. Tak więc w tym sensie G&W jest optymalna (zakładając również, że ).$P\neq NP$

3. Niektóre rozproszone algorytmy mogą być optymalne w odniesieniu do niektórych warunków (np. Odsetek procesorów przeciwnych), ale skoro wspomniałeś o maszynach Turinga, to chyba nie tego rodzaju przykładów szukasz.

Załóżmy, że dane wejściowe są podane i poprosił aby zdecydować, czy maszyna RAM M kończy się wejściowym x po t krokach. Według twierdzenia o hierarchii czasowej optymalnym algorytmem do podjęcia takiej decyzji jest symulacja wykonania M ( x ) dla $w = \langle M, x, t \rangle$$M$$x$$t$$M(x)$$t$ kroków, które można wykonać w czasie .$O(t)$

(Uwaga: w przypadku maszyn Turinga symulacja wykonania wymaga wykonania kroków O ( t log t ) ; znamy tylko dolną granicę Ω ( t ) . Nie jest to zatem optymalne w przypadku maszyn Turinga).$M$$O(t \log t)$$\Omega(t)$

Istnieje kilka innych problemów, które zawierają wersję problemu zatrzymania jako podprzykład. Na przykład podjęcie decyzji, czy zdanie jest konsekwencją WS1S, wymaga czasu 2 ↑ ↑ O ( | θ | ) i jest to optymalne.$\theta$$2 \uparrow \uparrow O(|\theta|)$

Nie jestem pewien, co rozumiesz przez „nietrywialny”, ale co powiesz na to. . Dlatego ten język nie jest regularny, więc każda TM decydująca się na to musi działać w Ω ( n log n $L = \{0^{2^k} | k \geq 0\}$$\Omega(n \log n)$ . Prosty algorytm (przecinanie wszystkich pozostałych 0) jest optymalny.

Jeśli pozwalasz na problemy z dynamiczną strukturą danych, znamy niektóre algorytmy superliniowe optymalne pod względem czasu. Jest tak w modelu sondy komórkowej, który jest tak silny jak słowo RAM, tzn. Nie jest to model ograniczony, taki jak algebraiczne drzewa decyzyjne.

$A[1], \ldots, A[n]$

• $\Delta$$A[i]$$i$$\Delta$
• $\sum_{j = 1}^i{A[i]}$, given $i$

You can easily support both operations in $O(\log n)$ time with a data structure based on an augmented binary tree with $A[i]$ at the leaves. Patrascu and Demaine showed this is optimal: for any data structure there is a sequence of $n$ additions and prefix sum queries that must take $\Omega(n\log n)$ time total.

Another example is union find: start with a partition of $\{1, \ldots n\}$ into singletons, and keep a data structure that allows the two operations:

• Union: given $i$ and $j$, replace the part containing $i$ and the part containing $j$ with their union
• Find: given $i$, output a canonical element from the part containing $i$

Tarjan showed that the classical disjoint set forest data structure with the union by rank and path compression heuristics takes $O(\alpha(n))$ time per operation, where $\alpha$ is the inverse Ackermann function. Fredman and Saks showed this is optimal: for any data structure there exists a sequence of $n$ union and find operations which must take $\Omega(n\alpha(n))$ time.

Many streaming algorithms have upper bounds matching their lower bounds.

istnieją dwa dość podobne algorytmy wyszukiwania, które [rozumiem, że] są optymalne w oparciu o określone ograniczenia dotyczące kolejności / dystrybucji danych wejściowych. jednak prezentacje algorytmów zwykle nie podkreślają tej optymalności.

• złoty odcinek poszukiwanie maksimum lub minimum (ekstremum) funkcji unimodalnej. zakłada, że ​​wejście jest funkcją unimodalną. znajduje to średnio w czasie logarytmicznym. o ile pamiętam, może być dowód optymalności w książce Struktura i interpretacja programów komputerowych autorstwa abelsona i sussmana.

• wyszukiwanie binarne znajduje średnio punkt w logarytmicznym czasie na posortowanej liście, ale wymaga sortowania danych wejściowych.

^{cytuję wikipedię powyżej, ale nie ma ona dowodów na to, że są one optymalne, może publiczność może znaleźć inne odniesienia, które dowodzą optymalności.}

Many sublinear time algorithms have upper bounds matching their lower bounds.