Co to znaczy „Asymptotycznie bardziej wydajny”?

Co to znaczy, kiedy mówimy, że algorytm $X$ jest asymptotycznie bardziej wydajny niż $Y$ ?

• $X$ będzie lepszym wyborem dla wszystkich danych wejściowych.
• $X$ będzie lepszym wyborem dla wszystkich danych wejściowych oprócz małych danych wejściowych.
• $X$ będzie lepszym wyborem dla wszystkich danych wejściowych oprócz dużych danych wejściowych.
• $Y$ będzie lepszym wyborem dla małych nakładów.

Link do tego pytania jest tutaj.

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

Myślałem, że algorytm bardziej asymptotycznie wydajny powinien działać dla wszystkich danych wejściowych, ale nie dostaję powodu, dla którego „Działa dla wszystkich danych wejściowych z wyjątkiem małych”.

Po pierwsze, oba algorytmy „działają” dla wszystkich danych wejściowych. Pytanie dotyczy wydajności.

Odpowiedzi na to pytanie są trochę gówniane. Jednym ze sposobów na stwierdzenie, że jeden algorytm jest asymptotycznie bardziej wydajny, jest inny, jeśli istnieje jakiś (specyficzny dla problemu) rozmiar wejściowy taki, że dla każdego większego rozmiaru wejściowego bardziej wydajny algorytm wykona mniej „kroków obliczeniowych”, zwykle za pomocą pewnej abstrakcyjnej miary, np. liczba porównań.

Ideą odpowiedzi jest to, że asymptotycznie bardziej wydajny algorytm może nadal wymagać więcej kroków przed tym rozmiarem wejściowym. To może być przypadek, że asymptotycznie bardziej wydajny algorytm wymaga mniej czynności dla wszystkich wejść, ale to nie musi być tak, aw praktyce zazwyczaj nie jest. Lepszym sformułowaniem „poprawnej” odpowiedzi byłoby „$X$będzie lepszym wyborem dla wszystkich danych wejściowych, z wyjątkiem możliwie małych danych wejściowych ”.

Sformułowanie wciąż nie jest jednak świetne. Po pierwsze, wiele innych czynników decyduje o tym, który algorytm jest „lepszym wyborem”, ale dam im, że w tym przypadku intencja jest wystarczająco jasna. Prawdziwy problem to „mały” i „duży”. Jednym z moich ulubionych artykułów jest najszybszy i najkrótszy algorytm dla wszystkich dobrze zdefiniowanych problemów . W tym artykule opisano algorytm, który podając dowolną specyfikację funkcji i dowód, że można ją obliczyć w czasie wielomianowym, obliczy tę funkcję w optymalnej złożoności czasowej ze współczynnikiem$5$plus dodatek. Na przykład, jeśli podałem mu implementację sortowania bąbelkowego jako specyfikację funkcji i prosty dowód, że tak było$O(n^2)$, wygeneruje algorytm sortowania, który był $O(n\lg n)$. W rzeczywistości stworzyłby algorytm, który był$5cn\lg n + o(n\lg n)$ gdzie $c$był stałym czynnikiem asymptotycznie ^* optymalnego algorytmu. To jest niesamowite. Jest tylko jeden problem: stały termin - ukryty w$o(n\lg n)$w tym przykładzie - czyni algorytm prawie na pewno całkowicie niewykonalnym dla praktycznie każdego rzeczywistego problemu. Co rozumiem przez „całkowicie nieosiągalny”? Mam na myśli, że śmierć termiczna wszechświata zdarzy się wiele razy, zanim ten algorytm się zakończy. Niemniej jednak dla odpowiednio „dużych” danych wejściowych będzie on szybszy niż sortowanie bąbelkowe. Chodzi mi o to, że prawie na pewno fizycznie nie jest możliwe zapisanie „odpowiednio dużego” wejścia, nie mówiąc już o obliczeniach.

W każdym razie, jak powiedziałbym poprawną odpowiedź, brzmiałby: „$X$ wymaga mniej kroków niż $Y$ przy wystarczająco dużych danych wejściowych. Jest to nadal nieco niejasne, ponieważ istnieje wiele pojęć „kroku”, które mogą mieć zastosowanie, a algorytm może być asymptotycznie bardziej wydajny w przypadku jednej metryki, a mniej wydajny w przypadku innej. Takie sformułowanie pozwala uniknąć oceny wartości „lepszy wybór ”; istnieje wiele powodów, aby wybrać asymptotycznie mniej wydajne algorytmy lub nawet mniej wydajne algorytmy, gdy określone są stałe czynniki / warunki, takie jak wydajność pamięci podręcznej lub prostota implementacji.

^* Tutaj jest subtelność. Algorytm optymalny asymptotycznie może mieć gorszy stały współczynnik,$c$, niż asymptotycznie nieoptymalny algorytm. Myślę, że będzie miał najlepszą wartość$c$ dla każdego algorytmu optymalnego asymptotycznie, ale można sobie wyobrazić, że aby wycisnąć niewielki wzrost wydajności asymptotycznej, dodaje się ogromną złożoność, która znacznie zwiększa stały współczynnik.

Co ludzie zwykle mają na myśli, gdy mówią coś takiego:

Gdyby $T_A$ i $T_B$ to dwie funkcje kosztowe algorytmów $A$ i $B$ odpowiednio w modelu X. $T_A \in o(T_B)$.

Obowiązuje tutaj wiele zastrzeżeń: $X$należy sprecyzować, a my musimy dokładnie zdefiniować, co to znaczy „koszt czasu pracy”. Czas prawie nigdy nie jest przedmiotem śledztwa. Istnieje wiele innych miar kosztów. Nie jest jasne, czy notacja Landaua zawiera jakieś pomocne stwierdzenie dotyczące wydajności. I tak dalej.

W szczególności żadne z proponowanych oświadczeń nie następuje, chociaż ludzie często sugerują, że tak było.

Niestety, szersza społeczność osób zajmujących się algorytmami przyjmuje terminologię, która jest pusta ze względu na prostotę. (Wykonywanie precyzyjnych i pomocnych instrukcji na temat algorytmów jest trudne!)

Możesz być zainteresowany naszymi pytaniami referencyjnymi .

Mówi się, że algorytm X jest asymptotycznie lepszy niż Y, jeśli X zajmuje mniej czasu niż y dla wszystkich wielkości wejściowych n większych niż wartość n0, gdzie n0> 0.

Zwróć uwagę, że nie jest to zwykła definicja! Gdyby$T_A(n) = n+1$ i $T_B(n) = n$nie powiedzielibyśmy, że jest „asymptotycznie lepszy”. Biorąc pod uwagę wszystkie zastrzeżenia analizy, która sprowadza wydajność algorytmu do jednej liczby, nie można twierdzić, że jeden był „lepszy” niż drugi.

Polecam uczyć się informatyki z zasobów CS, a nie od programistów, którzy kiedyś czytali o rzeczach na Wikipedii. (Tak, to trudne, ale widziałem zbyt wiele kłamstw propagowanych w kręgach programistów, nawet na SO).

„Asymptotycznie bardziej wydajny” oznacza „bardziej wydajny dla wszystkich problemów powyżej pewnego rozmiaru”. Nie mówi, co to jest „określony rozmiar” i nie mówi, co dzieje się przed tym „pewnym rozmiarem”.

Więc wszystkie odpowiedzi z wyjątkiem drugiej są wyraźnie błędne, ponieważ „Asymptotycznie bardziej wydajny” w ogóle nie mówi o małych rozmiarach wejściowych. Ale drugi jest również problematyczny.

Obecnie nie ma sprzętu, który mógłby przechowywać tablicę $10^{30}$ liczby całkowite, tak wyraźnie $10^{30}$liczby całkowite będą liczone jako „duże dane wejściowe”. Ale mogę łatwo stworzyć algorytm sortowania, który jest asymptotycznie bardziej wydajny niż Bubblesort, ale tylko dla danych wejściowych$10^{40}$lub więcej liczb całkowitych. Więc weź odpowiedź drugą, zmień „duże” na „wystarczająco duże”, a stanie się ona poprawna.

W praktyce często dobrym pomysłem jest sprawdzenie, dla którego rozmiaru wejściowego asymptotycznie lepszy algorytm jest rzeczywiście szybszy i jaki jest wymagany czas dla danych wejściowych, w których jest on szybszy, a czasami algorytm będzie szybszy tylko dla rozmiarów problemów, które praktycznie nie mogą i tak zostanie rozwiązany. Jeśli algorytm A pokonuje algorytm B, ale tylko w przypadku problemów, z których każdy bierze$10^{15}$ lat lub dłużej, to A nie jest bardzo pomocne.