Co oznacza szybszy algorytm w informatyce teoretycznej?

Jeśli istnieje algorytm działający w czasie $O(f(n))$ dla jakiegoś problemu A, a ktoś wymyśli algorytm działający w czasie, , gdzie , czy uważa się to za ulepszenie w stosunku do poprzedniego algorytmu?$O(f(n)/g(n))$$g(n) = o(f(n))$

Czy ma sens, w kontekście informatyki teoretycznej, wymyślić taki algorytm?

Nie, algorytm działający w czasie $O(f(n)/g(n))$ , gdzie $g(n) = o(f(n))$ , niekoniecznie jest uważany za poprawę. Na przykład załóżmy, że $f(n) = n$ i $g(n) = 1/n$ . Następnie oznacza gorsze ograniczenie czasowe niż O ( f ( n ) ) = O ( n ) .$O(f(n)/g(n)) = O(n^2)$$O(f(n)) = O(n)$

Aby ulepszyć algorytm działający w czasie , musisz opracować algorytm działający w czasie o ( f ( n ) ) , to znaczy w czasie g ( n ) dla niektórych funkcji g ( n ) = o ( f ( n ) ) .$f(n)$$o(f(n))$$g(n)$$g(n) = o(f(n))$

Jeśli wszystko, co wiesz, to że algorytm działa w czasie , nie jest jasne, czy algorytm działający w czasie O ( g ( n ) ) jest poprawą, niezależnie od f ( n ) , g ( n ) są. Wynika to z faktu, że duże O stanowi jedynie górną granicę czasu działania. Zamiast tego często bierze się pod uwagę złożoność najgorszego przypadku i szacuje się ją jako dużą Θ, a nie dużą$O(f(n))$$O(g(n))$$f(n),g(n)$$\Theta$ .$O$

Pamiętaj, że Notacja jest przeznaczona do analizy, w jaki sposób zadanie rośnie o różnej wielkości wejściowych, a konkretnie pomija czynniki multyplikatywnych, niższego rzędu okresie, a stałe.$O(...)$

Załóżmy, że masz algorytm , którego rzeczywisty czas działania wynosi 1 n 2 + 2 n + 1 (zakładając, że możesz liczyć instrukcje i znać dokładne czasy itd., Co jest oczywiście dużym założeniem we współczesnych systemach). Załóżmy, że opracowałeś nowy algorytm, którym jest O ( n ) , ale rzeczywisty czas działania wynosi 1000 n + 5000 . Załóżmy również, że wiesz, że oprogramowanie do korzystania z tego algorytmu nigdy nie zobaczy problemu o rozmiarze n $O(n^2)$$1n^2+2n+1$$O(n)$$1000n + 5000$ .$n>10$

A więc, który byś wybrał - algorytm , który zajmie 15 000 jednostek czasu, lub algorytm O ( n 2 ), który zajmie tylko 121 jednostek? Teraz, jeśli twoje oprogramowanie ewoluuje w zakresie rozwiązywania problemów o rozmiarach n > 100000 , który wybierzesz? Co byś zrobił, gdyby rozmiar problemu był bardzo różny?$O(n)$$O(n^2)$$n>100000$

Zasadniczo oznacza to, że dla każdego rozmiaru wejściowego, który jest wystarczająco duży, najgorszy przypadek działania starego algorytmu jest wolniejszy niż nowego. Jest to równoważne z formalizmem , gdzie g jest złożonością czasową nowego algorytmu, zaś f złożonością czasową starego.$g(n) \in o\bigl(f\left(n\right)\bigr)$$g$$f$

Czasami jednak informatykom zależy na przeciętnej wydajności. Klasycznym przykładem jest Quicksort: jego najgorszym czasem działania jest podczas gdy znamy inne, które działają w Θ ( n log n $\Theta(n^2)$$\Theta(n \log n)$ , ale jest szeroko stosowane w praktyce ze względu na dobry średni czas działania. Można go dodatkowo dostosować, aby działał bardzo szybko w przypadkach najczęściej występujących na wolności, takich jak tablice, które są w większości we właściwej kolejności.

A czasami nawet teoretyczni informatycy używają „szybciej” w taki sam sposób, jak zwykli ludzie. Na przykład, większość implementacji klas String ma Optymalizację Krótkiego Ciągu (zwaną również Optymalizacją Małych Ciągów), mimo że przyspiesza to tylko dla krótkich ciągów i jest czystym narzutem dla dłuższych. Ponieważ rozmiar wejściowy staje się coraz większy, czas działania operacji String z SSO będzie dłuższy o mały stały okres, więc zgodnie z definicją podaną w pierwszym akapicie usunięcie SSO z klasy String powoduje, że „szybciej” . ”W praktyce jednak większość ciągów znaków jest niewielka, więc SSO sprawia, że ​​większość programów, które ich używają, jest szybsza, a większość profesorów informatyki wie, że lepiej się nie kręcić, domagając się, aby ludzie mówili tylko o rzędach asymptotycznej złożoności czasu.

Nie ma jednej ujednoliconej definicji „szybszego algorytmu”. Nie ma organu zarządzającego, który decydowałby, czy algorytm jest szybszy niż inny.

Aby wyjaśnić, dlaczego tak jest, chciałbym przedstawić dwa różne scenariusze, które pokazują tę mętną koncepcję.

Pierwszy przykład to algorytm, który wyszukuje połączoną listę nieuporządkowanych danych. Jeśli mogę wykonać tę samą operację z tablicą, nie mam wpływu na dużą miarę wydajności Oh. Oba wyszukiwania mają wartość O (n). Jeśli popatrzę tylko na duże wartości Oh, mogę powiedzieć, że wcale nie poprawiłem. Jednak wiadomo, że przeszukiwanie tablicy jest szybsze niż przeszukiwanie połączonej listy w większości przypadków, więc można zdecydować, że dzięki temu algorytm stał się „szybszy”, nawet jeśli duże Oh się nie zmieniło.

Jeśli mogę użyć tradycyjnego przykładu programowania robota do zrobienia kanapki PBJ, mogę pokazać, co mam na myśli w inny sposób. Rozważ tylko punkt, w którym otwiera się słoik masła orzechowego.

Pick up the jar
Grab the lid
Unscrew the lid

Przeciw

Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid

Nawet w najbardziej akademickim otoczeniu teoretycznym, jakie mogę wymyślić, przekonasz się, że ludzie akceptują to, że pierwszy algorytm jest szybszy niż drugi, nawet jeśli wyniki dużej notacji Oh są takie same.

Dla kontrastu możemy rozważyć algorytm do złamania szyfrowania RSA. Obecnie uważa się, że ten proces to prawdopodobnie O (2 ^ n), gdzie n jest liczbą bitów. Rozważ nowy algorytm, który działa n ^ 100 szybciej. Oznacza to, że mój nowy proces działa w O (2 ^ n / n ^ 100). Jednak w świecie kryptografii przyspieszenie wielomianowe algorytmu wykładniczego nie jest tradycyjnie uważane za przyspieszenie teoretyczne. Robiąc dowody bezpieczeństwa, zakłada się, że osoba atakująca może odkryć jedno z tych przyspieszeń i że nie przyniesie to żadnego efektu.

Tak więc w jednym przypadku możemy zmienić O (n) na O (n) i nazwać to szybciej. W innych okolicznościach możemy zmienić O (2 ^ n) na O (2 ^ n / n ^ 100) i twierdzić, że w ogóle nie było znaczącego przyspieszenia. Dlatego mówię, że nie ma jednej ujednoliconej definicji „szybszego algorytmu”. Jest to zawsze zależne od kontekstu.

$A(n) \in O(f(n))$

$$\exists \ 0 \le c_f \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{f(n)} = c_f$$

$g(n)$$\limsup_{n\to\infty} g(n) = \infty$$h(n) = \frac{f(n)}{g(n)}$ .

$A'(n)$$O(h(n))$$A(n)$$O(h(n))$

$$\exists \ 0 \le c_h \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{h(n)} = c_h$$

Korzystając z reguł limitów, możemy również napisać:

$$c_h = \limsup_{n \to \infty} \frac{A(n)}{h(n)} = \limsup_{n \to \infty} \frac{A(n)g(n)}{f(n)} = c_f \cdot \limsup_{n \to \infty} g(n)$$

$c_h \lt \infty$$c_f = 0$

$c_f \neq 0$$A(n) \notin O(h(n))$ .

$A'(n)$$A(n)$$A(n) \in \Theta(f(n))$$g(n)$ jest arbitralnie wzrasta.

$A(n) \in O(f(n))$$A'(n)$$A(n)$$O(h(n))$