Uzasadnienie zaniedbania stałych czynników w Big O

Wiele razy, jeśli złożoność ma stałe, takie jak 3n, pomijamy tę stałą i mówimy O (n), a nie O (3n). Nie jestem w stanie zrozumieć, jak możemy zaniedbać taką trzykrotną zmianę? Niektóre rzeczy zmieniają się 3 razy szybciej niż inne! Dlaczego zaniedbujemy ten fakt?

Aby zracjonalizować sposób, w jaki notacje asymptotyczne ignorują czynniki stałe, zwykle myślę o tym w ten sposób: złożoność asymptotyczna nie służy do porównywania wydajności różnych algorytmów, lecz do zrozumienia, w jaki sposób wydajność poszczególnych algorytmów skaluje się względem wielkości wejściowej.

Na przykład mówimy, że funkcja, która wykonuje kroki to , ponieważ z grubsza mówiąc, dla wystarczająco dużych danych wejściowych, podwojenie wielkości wejściowej nie będzie więcej niż podwoić liczbę wykonanych kroków. Podobnie, oznacza, że ​​podwojenie wielkości wejściowej co najwyżej czterokrotnie zwiększy liczbę kroków, a oznacza, że ​​podwojenie wielkości wejściowej zwiększy liczbę kroków o najwyżej pewną stałą.O ( n ) O ( n 2 ) O ( log n $3n$$O(n)$$O(n^2)$$O(\log n)$

Jest to narzędzie do stwierdzania, które algorytmy skalują się lepiej, a nie które są absolutnie szybsze.

Po pierwsze, jak już wyjaśniono inne odpowiedzi, lub, mówiąc słowami, funkcją jest wtedy i tylko wtedy, gdy jest . oznacza, że ​​istnieje punkt i współczynnik taki, że dla wszystkich , . Teraz wybierz : dla wszystkich , , więc . Dowód przeciwny jest podobny.O ( 3 n ) O ( n ) f = O ( 3 n ) N C 3 n ≥ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$C 1 = 3 C 3 n ≥ N f ( n ) ≤ C 1 ⋅ n $f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Teraz powód, dla którego jest to właściwe narzędzie. Zauważ, że kiedy mierzymy złożoność algorytmu, nie podajemy jednostki. Nie liczymy sekund ani instrukcji maszynowych: liczymy niektóre nieokreślone elementarne kroki, z których każdy zajmuje ograniczony czas. Robimy to, ponieważ wykonanie tego samego algorytmu na innej maszynie zmieniłoby czas potrzebny na instrukcję - pomnożenie częstotliwości zegara przez a czas wykonania zmienia się od do . Jeśli zaimplementujemy ten sam algorytm w innym języku lub w innym systemie, czas potrzebny na każdy elementarny krok może być inny, ale znowu to zbyt wiele szczegółów: prawie nigdy nie dbamy o takie różnice.f ( n ) f ( n ) /$3$$f(n)$$f(n)/3$

Kiedy zależy Ci na precyzyjnych czasach, złożoność asymptotyczna nie ma znaczenia: złożoność asymptotyczna mówi ci, co dzieje się w przypadku bardzo dużych rozmiarów wejściowych, które mogą, ale nie muszą być rzeczywistymi rozmiarami wejściowymi, z którymi masz do czynienia.

Przypomnijmy definicję Big-O:

c > 0 f ( n ) ≤ c g ( n ) $f(n)\in O(g(n))$ iff istnieje takie, że dla wszystkich .$c>0$$f(n)\le cg(n)$$n$

Zgodnie z tą definicją mamy dla każdej stałej . Celem notacji jest właśnie uproszczenie wyrażeń w ten sposób. Rzeczywiście, rośnie 3 razy szybciej niż , ale oba są liniowe. Czy jest to uzasadnione, czy nie - zależy to od kontekstu. Ale jeśli zgadzasz się na użycie notacji , to z definicji ma to zastosowanie.d O 3 n n $dn\in O(n)$$d$$O$$3n$$n$$O$

Notacja Big O jest jednostkowym środkiem pomiaru zmienności wydajności, a zatem jest nieprzepuszczalna dla względnych kosztów prymitywów obliczeniowych.

W skrócie: notacja Big O jest jednostkowym, względnym rodzajem pomiaru (w przeciwieństwie do pomiaru bezwzględnego). Może mierzyć tylko zmienność wydajności, a nie wydajność absolutną, dla której stałe mają duże znaczenie. Zaletą jest to, że czyni to w dużej mierze niezależnym od implementacji, umożliwiając prostszą analizę, która może ignorować względne koszty operacji elementarnych, o ile koszty te mają dodatnią stałą górną i dolną granicę. Ale konsekwencją jest to, że stałe czynniki nie mają znaczenia . Mimo to, nawet pod kątem zamierzonego celu, asymptotyczna analiza złożoności może być kwestionowana na innych podstawach i należy ją rozpatrywać ostrożnie. Na przykład surowy rozmiar wejściowy może nie być właściwym parametrem do rozważenia.

Pierwsza uwaga jest taka, że ​​twoje pytanie nie jest dokładnie określone. Kiedy zaniedbujesz stałą w , rzeczywiście następuje „trzykrotna zmiana”, ale obie zmieniają się w tym samym tempie i nie możesz twierdzić, że „[jedna] rzecz zmienia się 3 razy szybciej niż inna”.3 $3$$3n$

Dobrym powodem do zignorowania stałej w notacji Landau jest to, że nie mamy jednostki, na której można polegać. Kiedy ktoś twierdzi, że A mieszka dwa razy dalej od ciebie niż B, ma to znaczenie niezależnie od dowolnej jednostki. Możemy się z tym zgodzić, nawet jeśli mierzysz odległości w calach, a ja robię to w latach świetlnych. Ale bezwzględny pomiar odległości wymaga podania jednostek, a jego sformułowanie liczbowe zależy od wybranej jednostki.

Rzeczywisty czas potrzebny algorytmowi zależy od czasu wykonywania operacji elementarnych, który jest bardzo zależny od maszyny. Można policzyć liczbę operacji elementarnych, ale nie ma powodu, aby sądzić, że wszystkie zajmują ten sam czas, i zawsze można połączyć kilka operacji w jedną lub odwrotnie, rozłożyć operację na mniejsze, aby liczba operacji nie ma większego znaczenia, chyba że zgadzasz się na referencyjną maszynę wirtualną. Zaletą jest niezależność od odniesień.

Innym poglądem na korzyść tego podejścia jest to, że w analizie liczy się tylko liczba operacji elementarnych, o ile ich koszt ma górną granicę i dodatnią dolną granicę. Nie musisz się martwić o indywidualne koszty.

Jednak cena za tę korzyść polega na tym, że ocena kosztów obliczeń jest podawana z nieokreśloną jednostką, a czas obliczeń może na przykład być nanosekundą lub tysiącleciem - nawet nie próbujemy tego wiedzieć. Innymi słowy, współczynniki stałe są bez znaczenia, ponieważ zmiana jednostek jest nierozerwalnie związana ze zmianą współczynnika stałego i nie stosuje się jednostek odniesienia.

Jak zauważył Patrick87 , to wystarczy, aby zrozumieć, jak algorytm skaluje się w odniesieniu do wielkości wejściowej, ale nie da absolutnej miary wydajności, bez polegania na jednostce odniesienia. Odłączenie wspólnej referencyjnej maszyny abstrakcyjnej można zrobić, gdy rzeczywiście chce się porównać wydajność różnych algorytmów, ale trudniej jest upewnić się, że porównanie nie jest stronnicze ze względu na szczegóły realizacji. W asymptotycznej złożoności tego ryzyka unika się, ponieważ porównujesz algorytm z samym sobą.

W każdym razie tylko naiwny programista polegałby wyłącznie na asymptotycznej złożoności przy wyborze algorytmu. Istnieje wiele innych kryteriów, w tym niezliczona stała i faktyczny koszt operacji elementarnych. Ponadto złożoność najgorszego przypadku może być złym wskaźnikiem, ponieważ źródło złożoności najgorszego przypadku może występować rzadko, a na fragmentach danych wejściowych na tyle małe, że ma ograniczony wpływ. Na przykład ogólne parsery gramatyki przylegającej do drzewa mają teoretyczną złożoność i są całkiem użyteczne w praktyce. Najgorszym przypadkiem, jaki znam, jest wnioskowanie o typie polimorficznym typu Damas-Hindley-Milner$O(n^6)$algorytm zastosowany dla ML, który ma wykładniczą najgorszą złożoność. Ale to nie przeszkadza użytkownikom ML ani nie zapobiega pisaniu bardzo dużych programów w ML. Liczy się coś więcej niż stała. W rzeczywistości analiza asymptotyczna wiąże miarę kosztu obliczeń z pewną miarą złożoności danych wejściowych. Ale surowy rozmiar może nie być właściwym miernikiem.

Złożoność jest jak rozstrzygalność, może być teoretycznie zła, ale może to nie mieć znaczenia dla większości przestrzeni danych ... czasami. Analiza asymptotycznej złożoności jest dobrym i dobrze zaprojektowanym narzędziem, z jego zaletami i ograniczeniami, jak wszystkie narzędzia. Z wyjaśnieniem stałej lub bez niej, co może być bez znaczenia, konieczne jest użycie osądu.

Pozostałe odpowiedzi stanowią doskonałe wyjaśnienie, dlaczego zgodnie z definicją Big-O, .$O(n)=O(3n)$

Jeśli chodzi o to, dlaczego tak robimy w CS, mamy tak zwięzły opis wydajności algorytmu. Na przykład może istnieć algorytm z instrukcją if, w którym jedna gałąź wykonuje instrukcji, a druga wykonuje instrukcje . Oznacza to, że dokładna liczba zmienia się dla każdego wejścia, nawet dla wejść tej samej długości. Możemy znaleźć liczbę dla każdego wejścia, ale użycie notacji big-O daje nam miarę złożoności czasu, która obowiązuje dla WSZYSTKICH danych wejściowych.3 $n$$3n$

Jest to o wiele bardziej przydatne w odgadywaniu szybkości działania algorytmu. W przeciwnym razie musielibyśmy przyjrzeć się ogromnej częściowej funkcji, która byłaby bardzo trudna do zrozumienia.

Innym głównym powodem jest to, że pomiary te są niezależne od sprzętu. Różne kompilatory i architektury zamieniają ten sam kod w bardzo różne zestawy instrukcji. Jeśli jednak wiemy, że liczba instrukcji jest liniowa, wykładnicza itp., Mamy pojęcie o szybkości algorytmów, niezależnie od tego, na jakim komputerze kompilujemy lub uruchamiamy.

$f(n)=O(g(n))$ oznacza .$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

Jeśli jest to prawdą dla , jest to również prawdą dla i odwrotnie.$g(n)=n$$g(n)=3n$

Podobnie . Tutaj równość oznacza, że należy do LHS iff należy do RHS. Znak tutaj jest poważnym nadużyciem notacji że ja osobiście nienawidzę, bo to jest mylące.f $O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$$f$$=$

Pozwól, że ci wyjaśnię. Weźmy n = 100000. Co to jest 3n? To jest 300000 ( Tak, to 3-krotnie n ) Ale co to jest n ^ 2 ? 10000000000 . ( jest to 1 lakh fałdów n ) .. Porównaj n ^ 2 z n. 3 jest nieistotne, gdy porównamy z 1 lakh. więc możemy to usunąć.

Pomyśl, czy n to jakieś miliardy lub tryliony. W tym przypadku ponownie porównamy 3 z niektórymi miliardami lub trylionami. Teraz wiesz, dlaczego możemy zaniedbać 3.