Co to jest wydajny algorytm?

Z punktu widzenia zachowania asymptotycznego, co jest uważane za „wydajny” algorytm? Jaki jest standard / powód rysowania linii w tym punkcie? Osobiście uważałbym, że wszystko, co naiwnie nazwałbym „sub-wielomianem”, takie jak$f(n) = o(n^2)$ Jak na przykład $n^{1+\epsilon}$ byłby wydajny i wszystko, co jest $\Omega(n^2)$byłoby „nieefektywne”. Jednak słyszałem, że wszystko, co należy do dowolnego wielomianu, można nazwać wydajnym. Jakie jest uzasadnienie?

To zależy od kontekstu. W informatyce teoretycznej zazwyczaj każdy algorytm wielomianu czasowego jest uważany za „wydajny”. W algorytmach aproksymacyjnych na przykład czas działania$n^{1/\epsilon^{1/\epsilon}}$ byłby uważany za wydajny, nawet jeśli nie będzie w praktyce przydatny dla żadnej rozsądnej wartości $\epsilon$. Algorytm dla SAT, który działa$n^{2^{100}}$ byłby niesamowitym przełomem.

W klasycznych algorytmach, tj. Algorytmach z lat 80. i wcześniejszych, środowiska wykonawcze poniżej $n^3$lub mniej więcej (pomyśl mnożenie macierzy, minimalne dopasowanie kosztów, przepływy, programowanie liniowe) są uważane za wydajne. Powiedziałbym, że nadal są one uważane za skuteczne przez większość ludzi. Oczywiście a$n^2$ algorytm nie jest uważany za wydajny, jeśli: $n\log n$ algorytm jest znany, na przykład do sortowania.

Obecnie istnieje trend w kierunku algorytmów podliniowych lub algorytmów przesyłania strumieniowego, które są w stanie poradzić sobie z terabajtami danych. Spróbuj użyć mnożenia macierzy, aby obliczyć ranking stron wszystkich stron w indeksie Google. To nie zadziała.

Oczywiście, choć zdecydowanie użyteczne, asymptotyczne środowisko uruchomieniowe algorytmu nie opowiada całej historii. Istnieją algorytmy z dobrym asymptotycznym środowiskiem uruchomieniowym, ale stałe, które są tak ogromne, że nie można ich skutecznie użyć. Zawsze. Lipton nazywa je Algorytmami Galaktycznymi . Robert Sedgewick twierdzi nawet, że granice najgorszych przypadków są „często bezużyteczne do przewidywania, często bezużyteczne dla gwarancji”, a „analiza najgorszych przypadków jest bezużyteczna do przewidywania wyników” w swoim przemówieniu „Powrót nauki do informatyki” .

Moje 2 centy z punktu widzenia algorytmów rozproszonych: patrząc na sieci wielkoskalowe (P2P, sieci społecznościowe itp.) Algorytm rozproszony jest uważany za wydajny, jeśli jego czas działania wynosi$O(\log^c n)$ dla jakiejś stałej $c>0$ a algorytm wykorzystuje wiadomości z$O(\log n)$bitów Należy zauważyć, że wymaganie dotyczące rozmiarów wiadomości jest zwykle przypisywane nawet większemu znaczeniu niż czas działania, w szczególności w przypadku problemów „globalnych”, które mają większą dolną granicę czasu działania, np. Rozproszony MST.

Powodem jest to, że z perspektywy zachowania asymptotycznego wielomianowe tempo wzrostu jest trywialnie niższe niż wielobiegunowe tempo wzrostu. W praktyce algorytm czasu wielomianowego działa znacznie szybciej niż super-wielomianowy algorytm czasu, gdy rośnie wielkość wejściowa.

Oczywiście nikt nie powiedziałby, że algorytm o złożoności wielomianowej, na przykład, $O(n^{2000})$ jest „wydajny”, ale większość algorytmów rzadko przekracza złożoność $O(n^5)$.

Praktyczne względy mogą nawet doprowadzić cię do tego $O(n^2)$jest nieefektywny w przetwarzaniu bardzo dużych danych wejściowych, dlatego staramy się udowodnić dolne granice i zaprojektować sekwencyjne algorytmy pasujące do tych dolnych granic z jednej strony, a następnie zastosować algorytmy równoległe z drugiej strony. W przypadku niektórych problemów, jeśli jesteś skłonny zaakceptować gwarancję probabilistyczną, możesz nawet skorzystać z sublinearnych algorytmów czasu (bardzo szybki, ale może nie dostarczyć poprawnej odpowiedzi z bardzo małym prawdopodobieństwem).

Teoretycznie uważa się, że algorytm jest wydajny, jeśli jego najgorszy czas działania jest ograniczony wielomianem na długości wejściowej. Powodem jest to, że wielomiany mają ładne właściwości zamykania. Dodawanie, mnożenie, komponowanie wielomianów to operacje, które dają wielomiany, i są one dobre, jeśli redukujesz problemy do siebie.

Oczywiście różnica między wielomianem a wykładnikiem staje się bardzo duża, ponieważ długość wejściowa rośnie, więc algorytmy czasu wielomianowego są znacznie lepsze. W praktyce algorytm wielomianowy może zająć dużo czasu przed zakończeniem, ale może się zdarzyć, że jest to algorytm optymalny (najlepszy z możliwych), w którym to przypadku powiedziałbym, że jest wydajny.

Niektóre problemy są łatwe, inne trudne. To, czy algorytm jest „wydajny”, zależy od tego, jak dobry jest w porównaniu z wrodzoną złożonością problemu. Jeśli znajdziesz algorytm uwzględniający dowolną liczbę n cyfr w O ($n^3$) i znajduję algorytm sortujący n liczb w O ($n^2$), wtedy twój algorytm jest bardziej wydajny (ponieważ pokonuje wszystko, co znane ludzkości przez ogromny czynnik, podczas gdy mój jest tak wolny, jak można oczekiwać od absolutnego początkującego).