9

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)$

— bv_Martn
źródło

1

Nie ma istotnej różnicy między O (5n ^ 2) a O (3n ^ 2) podczas analizy asymptotycznej. Oba mają wartość O (n ^ 2) i różnią się jedynie stałą. W rzeczywistości możesz nawet zredukować O (5n ^ 2) do O (3n ^ 2) lub O (n ^ 2), aby matematyka była czystsza, ponieważ są one równoważne. Pisząc dowód, notujesz na pasku bocznym, że są one równoważne. W rzeczywistości możesz nawet zamienić O (log n) na O (n) i zauważyć, że O (log n) <= O (n) na pasku bocznym. Uwaga na pasku bocznym informuje czytelnika, że jest celowa, a nie literówka. (Przynajmniej tak zrobiłem, gdy wziąłem Analiza Algorytmu na studiach).

— jww

2

Jeśli używasz notacji aby pozbyć się małych czynników, zawsze możesz napisać coś w stylu „... poprawia czas działania z do ”itp. Lub, równoważnie, i . Niektórzy autorzy wolą napisać jako skrót od pierwszego. Zobacz na przykład podręcznik Trefethena i Bau.

O (\cdot)

$O(\cdot)$

5 n^{2} + o (n^{2})

$5n^2 + o(n^2)$

3 n^{2} + o (n^{2})

$3n^2 + o(n^2)$

(5 + o (1)) n^{2}

$(5 + o(1))n^2$

(3 + o (1)) n^{2}

$(3 + o(1))n^2$

\sim 5 n^{2}

$\sim 5n^2$

— Yonatan N,

21

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)$

— John L.
źródło

1

@bv_Martn Oto dobry link, aby zrozumieć, co definiuje się notację (tylko prosty rachunek kalkulacyjny !): math.stackexchange.com/questions/925053/…

O (n)

$O(n)$

— Akshat Mahajan

2

Jedyny raz, kiedy widziałem stałe czynniki w notacji wielkiej-O, to kiedy ktoś chce stwierdzić, że chociaż dwa algorytmy mają tę samą klasę złożoności, jeden z nich jest ściśle szybszy od drugiego.

— Mark

7

@AkshatMahajan Jedyna odpowiedź na to pytanie /math/925053 jest po prostu błędna. Istnieje wiele wiarygodnych źródeł o dużych adnotacjach.

O

$O$

— John L.,

1

„Prawidłowe jest stwierdzenie, że złożoność czasowa algorytmu została poprawiona z 5n ^ 2 do 3n ^ 2” - chociaż dokładny czas działania często zmienia się dla różnych wielkości wejściowych i wartości. Obejmuje to także ważenie wszystkich operacji / koncentrowanie się na jednej operacji, co może nie mówić wiele o stałych czynnikach, które można uzyskać w świecie rzeczywistym, lub być porównywalne z innymi algorytmami używającymi różnych wag. Tak więc, chociaż może mieć kilka poprawnych przypadków użycia, powiedzenie czegoś takiego jak powyższe ma ograniczoną przydatność (prawdopodobnie dlatego rzadko się go widuje).

— Bernhard Barker,

1

@ Mark: To po prostu źle.

— user21820

13

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ę.

— Juho
źródło

Nie potrzebuję tego jeszcze w praktyce. Lub teoretycznie właściwie, muszę tylko wiedzieć, czy podane przez wikipedię definicje O (1) -O (n!) Są jedynymi, które istnieją, czy też w rzeczywistości można je inaczej opisać, jeśli są różne, takie jak O (7N). Obawiam się, że jeśli

— użyję

1

Istnieje dowolna definicja, którą tworzy każdy. Powinieneś bardzo uważnie przeczytać, co oznacza notacja lub , Ponieważ twoje pytanie nie ma sensu. Brak skrótów. Jeśli chcesz zrozumieć, co oznacza kawałek treści matematycznych, musisz zainwestować trochę czasu.

O (1)

$O(1)$

O (n!)

$O(n!)$

— Juho

6

@bv_Martn Profesor matematyki ma większe szanse na odrzucenie, ponieważ przeglądasz listę przykładów jako listę definicji. Matematyka polega na tym, aby definiować rzeczy w taki sposób, aby działały one ogólnie, a nie tylko w określonych przypadkach. Twoje pytanie jest w zasadzie bardziej zaawansowaną wersją „Wikipedia mówi, że mogę dodać jeden i dodać dwa i siedemnaście. Ale czy mogę również dodać inne liczby?”

— David Richerby,

7

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.

— rozpraszać
źródło

5

Największym problemem z tego typu odpowiedzią jest to, że nie dotyka definicji Big Oh, ale po prostu używa jej jako pewnego rodzaju intuicyjnej magii, jak w „patrz, kiedy to robisz i to, to ”. Osobiście uważam, że o wiele bardziej pouczające jest powiedzenie komuś, że Big Oh absolutnie nie ma absolutnie nic wspólnego z algorytmami i zacząć od tego.

O (n)

$O(n)$

— Juho

3

@Jhoho może pouczający, ale ostatecznie bezużyteczny dla zdecydowanej większości informatyków.

— rozproszyć

4

Z tym muszę się nie zgodzić. Określenie siebie jako informatyka nie powinno być usprawiedliwieniem dla niezrozumienia, co oznacza kawałek notacji, którą się stosuje, tj. Pominięcia całej matematyki.

— Juho

3

Tak. Nie mam żadnych zastrzeżeń do programistów nie Zrozumienie tej rzeczy, ale jeśli chcesz nazywać się komputera naukowca , to jest materiał rdzenia.

— David Richerby,

2

@dkaeae Nie, mam na myśli osoby, które pracują w innych zawodach, np. twórców oprogramowania.

— rozproszyć

5

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$

— David Richerby
źródło

4

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)).

— gnasher729
źródło

4

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)$

— maniak zapadkowy
źródło

4

Konwencja o równości nie dotyczy pisania. Jest tak, ponieważ przydatność wyrażeń takich jak zachęca nas do postrzegania jako „zestawu funkcji takich, że [...] „i” niektóre funkcje takie, że [...] ”

\log (n!) = n \log n - n + O (\log n)

$\log (n!) = n\log n - n + O(\log n)$

O (f)

$O(f)$

— David Richerby,

Czy istnieją odmiany regularnych środowisk uruchomieniowych notacji Big-O-Notation?

Notacja Big-O opisuje skalowalność