Istnieje wiele Notacji, takich jak lub i tak dalej. Zastanawiałem się, czy w rzeczywistości istnieją odmiany takich jak lub , czy też są matematycznie niepoprawne.$O$$O(n)$$O(n^2)$$O(2n^2)$$O(\log n^2)$

A może słuszne byłoby stwierdzenie, że można poprawić do ? Nie mogę i nie muszę jeszcze wymyślać środowisk uruchomieniowych i nie muszę niczego poprawiać, ale muszę wiedzieć, czy w ten sposób opisujesz swoje funkcje w rzeczywistości.$O(5n^2)$$O(3n^2)$

Zastanawiałem się, czy w rzeczywistości istnieją odmiany takich jak lub , czy też są matematycznie niepoprawne.$O(2n^2)$$O(\log (n^2))$

Tak, lub są prawidłowymi odmianami.$O(2n^2)$$O(\log (n^2))$

Jednak rzadko je zobaczysz, jeśli w ogóle je zobaczysz, szczególnie w końcowych wynikach. Powodem jest to, że to . Podobnie to . To może być zaskakujące dla początkujących. Jednak te równości są mniej więcej tym samym powodem, dla którego wprowadzono duże adnotacje, aby ukryć multiplikatywny stały czynnik, który często jest trudny do ustalenia i względnie nieistotny.$O(2n^2)$ $O(n^2)$$O(\log (n^2))$ $O(\log n)$$O$

Czy dobrze byłoby powiedzieć, że można poprawić do ?$O(5n^2)$$O(3n^2)$

To wcale nie jest poprawa, jeśli złożoność czasowa algorytmu zostanie zmieniona z na lub z na , ponieważ to podczas gdy to . Dlatego błędne jest twierdzenie, że złożoność czasowa została poprawiona z na . Prawdą jest, że złożoność czasowa algorytmu została poprawiona z do , oczywiście.$O(5n^2)$$O(3n^2)$$\Omega(5n^2)$$\Omega(3n^2)$$O(5n^2)$$O(3n^2)$$\Omega(5n^2)$$\Omega(3n^2)$$O(5n^2)$$O(3n^2)$$5n^2$$3n^2$

Ćwiczenie 1. Pokaż, że .$O(5n^2)=O(3n^2)=O(n^2)$

Ćwiczenie 2. Pokaż, że .$O(\log n)=O(\log (n^2))$

Ćwiczenie 3. Pokaż, że .$\Omega(n^2+n)=\Omega(n^2)$

Zawsze możesz w ogóle nie używać tego zapisu. Oznacza to, że możesz określić funkcję tak dokładnie, jak to możliwe, a następnie spróbować ją poprawić. Na przykład możesz mieć algorytm sortowania, który dokonuje porównań , więc możesz spróbować wymyślić inny algorytm sortowania, który wykonuje tylko porównania . Oczywiście istnieją wszelkiego rodzaju funkcje (teoretycznie), a także mogą pojawić się (w praktyce).$f(n)$$f(n)$$g(n)$$f(n)$

Zamiast traktować zapis Big Oh jako tajemniczą magię, w której musisz skonsultować się z czarodziejami, aby zapytać, czy możesz coś zrobić, powinieneś spojrzeć na jego definicję . Przestrzegaj definicji, a następnie rób wszystko, czego potrzebujesz, aby wykonać swoją pracę.

Chociaż przyjęta odpowiedź jest całkiem dobra, nadal nie dotyka prawdziwego powodu, dla którego .$O(n) = O(2n)$

Notacja Big-O opisuje skalowalność

Zasadniczo notacja Big-O nie jest opisem czasu działania algorytmu. Nie jest też opisem liczby kroków, linii kodu ani porównań, jakie wykonuje algorytm. Jest to najbardziej przydatne, gdy jest używane do opisania, jak algorytm skaluje się z liczbą danych wejściowych.

Weźmy na przykład wyszukiwanie binarne. Biorąc pod uwagę posortowaną listę, jak znaleźć w niej dowolną wartość? Możesz zacząć od środka. Ponieważ lista jest posortowana, środkowa wartość powie ci, na której połowie znajduje się twoja wartość docelowa. Zatem lista, którą musisz przeszukać, jest teraz podzielona na pół. Można to zastosować rekurencyjnie, a następnie przejść na środek nowej listy i tak dalej, aż rozmiar listy wyniesie 1 i nie znajdziesz wartości (lub nie ma jej na liście). Podwojenie wielkości listy dodaje tylko jeden dodatkowy krok do algorytmu, który jest relacją logarytmiczną. Zatem ten algorytm to . Logarytm to podstawa 2, ale to nie ma znaczenia - rdzeń związku polega na tym, że pomnożenie listy przez stałą wartość dodaje tylko stałą wartość do czasu.$O(\log n)$

Porównaj standardowe wyszukiwanie z nieposortowaną listą - jedynym sposobem na znalezienie wartości w tym przypadku jest sprawdzenie każdej z nich. Scenariusz najgorszego przypadku (co sugeruje konkretnie Big-O) jest taki, że twoja wartość znajduje się na samym końcu, co oznacza, że ​​dla listy rozmiarów musisz sprawdzić wartości. Podwojenie wielkości listy podwaja liczbę operacji, które musisz sprawdzić, co jest relacją liniową. . Ale nawet gdybyś musiał wykonać dwie operacje na każdej wartości, pewne przetwarzanie, na przykład, relacja liniowa nadal obowiązuje. po prostu nie jest użyteczny jako deskryptor, ponieważ opisałby dokładnie taką samą skalowalność jak .$n$$n$$O(n)$$O(2n)$$O(n)$

Rozumiem, że wiele z tych odpowiedzi w zasadzie mówi ci, abyś sam doszedł do tego wniosku, czytając definicję Big-O. Ale to intuicyjne zrozumienie zajęło mi sporo czasu, aby owinąć głowę i dlatego przedstawiam to tak jasno, jak to tylko możliwe.

Możesz napisać dla dowolnej funkcji i ma to sens. Zgodnie z definicją jeśli istnieje jakaś stała  taka, że dla wszystkich wystarczająco dużych  . Nic w tej definicji nie mówi, że musi być jakąś „ładną” funkcją.$O(f)$$f$$g(n)=O(f(n))$$c$$g(n)\leq c\,f(n)$$n$$f$

Jednak, jak odbierze już wspomniano, i opisano dokładnie w takiej samej sytuacji: jeśli dla wszystkich wystarczająco dużych  , wtedy mamy również , więc , również ( przyjmowanie stałej jako ).$g(n)=O(f(n))$$g(n)=O(2f(n))$$g(n)\leq c\,f(n)$$n$$g(n)\leq \tfrac{c}{2}2f(n)$$g(n)=O(2f(n))$$c/2$

Jako problem uboczny nie pisz „ ”, ponieważ nie jest w 100% jasne, co to znaczy. Można powiedzieć, że oczywiście oznacza to ale prawie wszyscy zapisaliby to jako , więc budzi to wątpliwości czytelnika.$\log n^2$$\log(n^2)$$2\log n$

Zauważ też, że notacja big- nie ma nic wspólnego ze środowiskiem wykonawczym per se . To tylko zapis relacji między funkcjami. Funkcje te są często używane do mierzenia czasu działania algorytmów, ale to tylko jedna aplikacja, podobnie jak mierzenie wysokości ludzi to tylko jedna aplikacja liczb.$O$

Spójrz na definicję O (f (n)), a zobaczysz, że na przykład O (2n ^ 2) i O (n ^ 2) są dokładnie takie same. Zmiana algorytmu z operacji 5n ^ 2 na 3n ^ 2 to 40-procentowa poprawa. Zmiana z O (5n ^ 2) na O (3n ^ 2) w rzeczywistości nie jest żadną zmianą, są one takie same.

Ponownie przeczytaj definicję O (f (n)).

Pomocne może być zrozumienie, że Big-O opisuje zestaw funkcji . To jest$O(f(n)) = \lbrace g(n) | \exists n,c>0: \forall m > n: c\times g(m) \le f(m)\rbrace$

Użycie jest trochę niefortunne, a użycie sprawiłoby, że ta relacja byłaby o wiele jaśniejsza. ale ustawione symbole notacji są nieco trudne do napisania, więc teraz utknęliśmy w obecnej konwencji.$=$$\in$

To pokazuje, że Lub że stałe czynniki nie mają znaczenia przy definiowaniu Big O.$O(n) = O(2n)$