Co to jest O w Big O?

23

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 ?

Karen15
źródło
13
Jest to piętnasta litera alfabetu angielskiego. Jest to także 15. litera alfabetu greckiego.
Joel Etherton
1
Żeby wyjaśnić: szukasz powodu, dla którego O jest używanym symbolem (zamiast Q, E lub czegoś innego) i jakie znaczenie, jeśli w ogóle, O ma nad innymi symbolami?
FrustratedWithFormsDesigner
6
@Jel: Właściwie to Omicron i to jest wskazówka, dlaczego wybrano ten konkretny list.
Jörg W Mittag,
ta odpowiedź obala (słusznie, jak sądzę) teorię Omicron.
Hawkeye Parker

Odpowiedzi:

31

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.

back2dos
źródło
5
Chociaż może się zdarzyć, że wielu matematyków tak to określiło, pierwotnie tak nie było. Jeśli czytasz książki z teorii liczb z początku XX wieku, nie znajdziesz takiego wyjaśnienia. Tak właśnie jest i nie potrafię czytać po niemiecku, żeby zrozumieć, co on myśli o notacji.
Jonathan Henson
1
@Jonathan: Post został zaktualizowany.
back2dos
Bardzo dobrze! Przejrzałem wszystkie moje książki z teorii liczb i nie mogłem nigdzie znaleźć wyjaśnienia O. +1
Jonathan Henson
2
Zawsze wymawiałem to jako kolejność, ponieważ samo powiedzenie O nie znaczy wiele.
Newtopian
16

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

Ethel Evans
źródło
5
Przykro mi, ale notacja Bachmanna-Landaua została wymyślona przez niemieckiego matematyka, więc nie sądzę, aby nazwał ją po angielskim słowie. W rzeczywistości, nawet gdyby został wymyślony przez amerykańskiego matematyka, prawdopodobnie nadal byłby nazwany na cześć niemieckiego słowa, ponieważ kiedy został wymyślony (wydaje mi się, że około 1920 r.), Międzynarodowym językiem matematyki był niemiecki. Plus, nie ma nawet zdalnie mieć nic wspólnego ze złożoności.
Jörg W Mittag,
1
@ Jörg: Tak, ale czy nie byłoby to po prostu Ordnung , o którym mówi niemiecki artykuł wiki: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
back2dos
1
@Ethel, czy mógłbyś wprowadzić niewielką zmianę w swoim artykule, abym mógł zagłosować? Naprawdę masz rację. Musisz edytować, zanim będę mógł głosować.
Jonathan Henson,
1
@Jonathan, nie jestem pewien, jakiej drobnej zmiany chcesz. Czy możesz po prostu dokonać zmiany, którą chcesz? Albo możemy po prostu pozwolić, aby odpowiedź back2dos pozostała, wygląda na to, że i tak skończyłby najlepszą odpowiedzią z powodu doskonałych badań :)
Ethel Evans
1
Hm, ciekawe. W Szwecji Big Oh jest zwykle nazywany „ordo” (po łacinie, no cóż, porządek), a nie „ordning” (szwedzkie słowo porządek).
Vatine
11

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.


źródło
2
Ciekawy. Przypuszczam, że masz rację. Właśnie przejrzałem definicje zarówno w książkach Landaua, jak i Bachmanna, a one rzeczywiście a) używają łacińskiego Oh, nie greckiego Omikron, b) oba używają słowa „Ordnung”, c) Landau wyraźnie stwierdza, że ​​oznacza to „Ordnung” . Poprawiono mnie.
Jörg W Mittag,
Jakie lepsze słowo można znaleźć? To znaczy z niemieckiego? Ordnung ist das halbe Leben!
JensG
Wydaje mi się, że pierwsze zdanie twojej (poprawnej, wzniosłej, niesamowitej) odpowiedzi powinno brzmieć: „O oznacza„ Ordnung ”(niem.„ Porządek ”). Pomogłoby to w uzyskaniu odpowiedzi innych czytelników.
Hawkeye Parker
5

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.

topgun_ivard
źródło
5
Sam link do artykułu nie jest zbyt pomocny. Zazwyczaj dobrym pomysłem jest sparafrazowanie lub zacytowanie sekcji, która jest szczególnie istotna dla wątku.
Demian Brecht,
3
Czy głosowanie w dół jest naprawdę konieczne? Artykuł, który zamieścił, jest bardzo istotny i IMHO bardzo pomocny. Tymczasem najczęściej głosowaną odpowiedzią jest link do artykułu w Wikipedii. +1, aby zrównoważyć hipokryzję umysłu-ula.
Brandon Moretz,
1
-1, ponieważ artice, choć jest bardzo ładnym i dobrze napisanym artykułem, nie ma nic wspólnego z pytaniem.
Jörg W Mittag,
@Jorg, nigdy nie mówiłem, że artykuł rozwiąże problem, ale podzieliłem się tym, ponieważ uznałem, że jest przydatny, gdy patrzę na te pojęcia.
topgun_ivard,
3
@topgun_ivard: Co się stanie, jeśli zmieni się w martwy link? Parafrazowanie pozwala 1) odbiorcom tego wątku uzyskać wersję linku z notatkami Colesa (czas to pieniądz), a 2) zapewnia, że ​​Twój post nie zostanie uznany za nieistotny dla martwego linku.
Demian Brecht
2

„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

Jonathan Henson
źródło
2

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

Jörg W Mittag
źródło
2
Chociaż chciałbym uwierzyć w twoją mnemoniczną propozycję (jest to naprawdę fajny pomysł), będę potrzebował jakiegoś dowodu, że taka jest pierwotna intencja Bachmanna. Podaj to, a dam ci +1.
Jonathan Henson
2
@Jonathan Henson: Najwyraźniej zostałem wprowadzony w błąd przez prof. Knutha :-)
Jörg W Mittag
-5

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

SoftwareSavant
źródło
2
-1, ponieważ jest to po prostu stara, niepoprawna ORAZ odpowiedź na osobne pytanie, niż zostało zadane. Pytanie brzmiało: dlaczego użyto litery „O”, a nie „jak działa notacja Big O?”. Mylisz się co do tego, jak działa Big-oh, chociaż ... zapętlanie tablicy jest O (n), gdzie n jest rozmiarem tablicy, a nie O (1). Notacja nie ma nic wspólnego z „cyklami” algorytmu ... to pomiar górnej granicy czasu działania algorytmu.
Casey Patton,
Nie kłócić się z tobą tutaj, ale o to mi chodziło. Co oznacza czas wykonywania, prawda? Czas pracy zależy od tego, co trzeba przetworzyć na komputerze. Wydaje mi się, że tutaj trochę używam cyklu. Wydaje mi się, że po cyklu powinienem był powtórzyć lub coś takiego. Masz rację co do górnej granicy, to nie określa średniej. Dlatego akceptuję obniżenie wersji.
SoftwareSavant,