Co to jest O w Big O?

Co to jest Big and O w notacji Big O? Przeczytałem definicje i nie mówi, co oznacza O jako „och”. Na przykład - rozumiem, że O (n) jest złożonością algorytmu liniowego, gdzie n może być liczbą operacji. ale czym jest O ?

Domyślam się, że to porządek, który pokrywa się z wikipedią .

Edycja: (moje własne (wszelkie ulepszenia docenione)) tłumaczenie z niemieckiego artykułu wikipedia

Wielka litera O (właściwie ówczesny omicron) jako symbol porządku (niemiecki: „Ordnung von”) została po raz pierwszy użyta przez niemieckiego teoretyka liczb Paula Bachmana w drugim wydaniu jego książki o teorii liczb analitycznych w 1894 r. notacja zyskała na popularności dzięki pracy Edmunda Landaua, innego niemieckiego teoretyka liczb, z którym ta nomenklatura jest dziś powszechnie związana, zwłaszcza w terminologii niemieckiej.

„Duży” oznacza „kapitał”, a „O” oznacza porządek, podobnie jak „porządek złożoności”. Tak nazwany ze względu na konwencję pisania „porządku złożoności” jako O (f (x)), np. Wielką literą „O” lub „Big O”. Nikt nie mówi o tym za dużo, ponieważ „wszyscy” rozumieją, co to znaczy, a zrozumienie go tak naprawdę nie pomaga zrozumieć analizy złożoności.

Dla zrozumienia analizy złożoności uważam, że link opublikowany przez topgun_ivard jest dobrym miejscem do rozpoczęcia. Pomocny może być również dobry podręcznik wprowadzający obejmujący struktury danych lub algorytmy.

O oznacza porządek.

Został on pierwotnie wprowadzony przez niemieckiego matematyka Paula Bachmanna w drugim tomie jego książek na temat teorii liczb Die Analytische Zahlentheorie , opublikowanym w 1894 r. (S. 401) . Zauważył, po formule, w której po raz pierwszy używa notacji:

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (...)

Moje tłumaczenie:

(...) gdzie za pomocą notacji O (n) wskazujemy wielkość, której rząd w odniesieniu do n nie przekracza rzędu n (...)

W przeciwieństwie do tego, co powiedzieli inni, nic w jego tekście nie wskazuje, że jest to w rzeczywistości omikron greckiej stolicy. Używa wielu greckich i łacińskich znaków, więc tak naprawdę nie ma sposobu, aby powiedzieć. Biorąc pod uwagę jego ciągłe używanie w tekście „Ordnung n log n ” itp., Jasne jest, że w każdym razie oznacza ono „Ordnung” (po niemiecku „porządek”, jeśli istniały jakiekolwiek wątpliwości), ale nadal może pozostawać otwarte fantazyjny grecki O.

Jednak pochodzenie omikronu jest prawdopodobnie bardziej retronimem ze względu na Donalda Knutha, który wprowadził symbole omega (Ω) i theta (Θ) dla pokrewnych pojęć w swojej pracy Big Omicron i Big Omega i Big Theta , a może Hardy i Littlewood, którzy wprowadził wcześniej symbol omega.

Podoba mi się ten artykuł , mam nadzieję, że również okaże się przydatny!

Cytując część artykułu:
Big Greek Letters

Duże O jest często niewłaściwie używane. Big O lub Big Oh to właściwie skrót od Big Omicron. Reprezentuje górną granicę asymptotycznej złożoności. Więc jeśli algorytmem jest O (n log n), istnieje stała c, tak że górną granicą jest cn log n.

Θ (n log n) (Big Theta) jest ściślej związany niż to. Taki algorytm oznacza, że ​​istnieją dwie stałe c1 i c2 takie, że c1n log n <f (n) <c2n log n.

Ω (n log n) (Big Omega) mówi, że algorytm ma dolną granicę cn log n.

Są inne, ale są one najczęstsze i Big O jest najbardziej powszechne ze wszystkich. Takie rozróżnienie jest zazwyczaj nieistotne, ale warto je zauważyć. W końcu poprawna notacja to poprawna notacja.

Co to jest Big O?

Notacja Big O ma na celu opisanie względnej złożoności algorytmu poprzez zmniejszenie tempa wzrostu do kluczowych czynników, gdy czynnik kluczowy zmierza w kierunku nieskończoności. Z tego powodu często usłyszysz wyrażenie asymptotyczne złożoność. W ten sposób wszystkie inne czynniki są ignorowane. Jest to względna reprezentacja złożoności.

Co to nie jest Big O?

Big O nie jest testem wydajności algorytmu. Jest także fikcyjny lub abstrakcyjny, ponieważ ignoruje inne czynniki. Złożoność algorytmu sortowania jest zwykle ograniczona do liczby elementów sortowanych jako kluczowy czynnik. Jest w porządku, ale nie bierze pod uwagę takich problemów, jak:

Wykorzystanie pamięci: jeden algorytm może zużywać znacznie więcej pamięci niż inny. W zależności od sytuacji może to być wszystko, od zupełnie nieistotnego do krytycznego; Koszt porównania: być może porównanie elementów jest naprawdę drogie, co potencjalnie zmieni jakiekolwiek rzeczywiste porównanie algorytmów; Koszt przeniesienia elementów: kopiowanie elementów jest zazwyczaj tanie, ale niekoniecznie tak jest; itp.

„f (x) jest duże-oh g (x)”

Jest to matematyczny sposób przewidywania wzrostu funkcji.

Niech f i g będą funkcjami od zbioru liczb całkowitych lub zbioru lub liczb rzeczywistych do zbioru liczb rzeczywistych. Mówimy, że f (x) to O (g (x)), jeśli istnieją stałe C i k takie, że | f (x) | <= C | g (x) | gdziekolwiek x> k.

Przeczytałbyś to, ponieważ „f (x) jest duże-oh g (x)”

Wielkie-O jest czasem nazywane symbolem Landaua od niemieckiego matematyka Edmunda Landaua. Nie sądzę, żeby to oznaczało coś poza tym. Masz również podobne notacje big-omega i big-theta. Symbole są tak arbitralne, jak zawsze, używając teta do oznaczenia kątów w twoich trójkątach w licealnej klasie geometrii planarnej.

Korekta @ back2dos dostarczyła satysfakcjonującego wyjaśnienia dla O jako odnoszącego się do zamówienia. Dobra robota. Zobacz jego odpowiedź.

Donald Knuth zastosował go do badania złożoności programów komputerowych.

Jeśli chcesz znaleźć powód zastosowania notacji, powinieneś przeczytać

„Analytische Zahlentheorie” Paula Bachmanna z 1892 r

EDYCJA: Okazuje się, że się mylę. Niemniej jednak może to pomaga komuś zachować proste symbole, więc nie zamierzam go usuwać.

Właściwie to nie jest łacińska litera Och , to grecka litera Omicron . Niestety, te dwa mają dokładnie ten sam glif, więc z czasem oryginalna wersja uległa uszkodzeniu, a teraz jest po prostu Oh .

Wybór symbolu w rzeczywistości nie ma żadnego szczególnego znaczenia, został wybrany jako urządzenie mnemoniczne :

• Omicron ma litery MICRO, a semantyka symbolu Omicron z grubsza oznacza „mniejszy niż”
• Omega ma w sobie litery MEGA, a semantyka symbolu Omega z grubsza oznacza „większy niż”
• Theta (Θ) wygląda trochę jak znak równości, a semantyka symbolu Theta z grubsza oznacza „równa się”

to jest to! Nie ma to żadnego znaczenia, to po prostu gra słów, jeśli chcesz, aby łatwiej zapamiętać semantykę.

AKTUALIZACJA: Próba oczyszczenia mojej odpowiedzi i dokładniejszego

Notacja Big O to sposób na scharakteryzowanie funkcji według tamtych wskaźników wzrostu. O oznacza porządek (pierwszy rząd to n drugi rząd to n-kwadrat itp.). A jeśli się nie mylę, byłby to najgorszy scenariusz dla środowiska uruchomieniowego metod (lub magazynu) dla N elementów. Im większa kolejność, tym gorsza jest metoda.
Na przykład wyszukiwanie rekordu w tablicy to O (1) (Wierzę w pewną implementację tablic mieszających, która również ma miejsce). Dodanie wartości na końcu listy linków byłoby O (N), ponieważ musisz dostać się na koniec listy, zanim będziesz mógł dodać element itp.

Ta odpowiedź powinna być nieco bardziej poprawna niż moja pierwsza próba :)