Co to jest O w Big O?

Cóż, przypuszczam, że kolejność, która pokrywa się z wikipedią .

Edytuj: (moje własne (mile widziane ulepszenia)) tłumaczenie z artykułu z niemieckiej Wikipedii

Wielka litera O (w tamtym czasie była to duża omikron) jako symbol rzędu (niem. „Ordnung von”) była po raz pierwszy używana przez niemiecki teoretyk liczb Paul Bachman w drugim wydaniu swojej książki o analitycznej teorii liczb ukazał się w 1894 roku. Popularność notacji przyniosła praca Edmunda Landaua, innego niemieckiego teoretyka liczb, z którym ta nomenklatura jest dziś powszechnie kojarzona, zwłaszcza w Terminologia niemiecka.

Komentarze

• Chociaż może się zdarzyć, że wielu matematyków wspomniało jako takie nie było tak pierwotnie. Jeśli czytasz książki o teorii liczb z początku XX wieku, nie znajdziesz takiego wyjaśnienia. Tak jest i nie mogę ' czytać po niemiecku, aby dowiedzieć się, co myśli o notacji.
• @Jonathan: Post zaktualizowany.
• Bardzo fajnie! Przejrzałem wszystkie moje książki o teorii liczb i nigdzie nie mogłem ' znaleźć wyjaśnienia O. +1
• I ' zawsze wymawiałem to jako kolejność , ponieważ samo powiedzenie O nie znaczy wiele.
• Bardzo pouczające! ale nadal – dlaczego O wymawiane jako ' oh ' przez programistów?

„Duże” oznacza „duże”, a „O” oznacza porządek, jak w „porządku złożoności”. Nazwany tak ze względu na konwencję pisania „porządku złożoności” jako O (f (x)), np. Wielką literą „O” lub „Wielkim O”. Nikt dużo o tym nie mówi, ponieważ „wszyscy” rozumieją, co to znaczy, a zrozumienie tego tak naprawdę nie pomaga w zrozumieniu analizy złożoności.

Myślę, że aby zrozumieć analizę złożoności, łącze zamieszczone przez topgun_ivard to dobre miejsce na rozpoczęcie. Pomocny może być również dobry podręcznik wprowadzający obejmujący struktury danych lub algorytmy.

Komentarze

• I ' przepraszam, ale notacja Bachmanna-Landau została wymyślona przez niemieckiego matematyka, więc nie sądzę, żeby nazwał ją po angielsku. W rzeczywistości nawet gdyby został wymyślony przez amerykański matematyk, prawdopodobnie nadal zostałby nazwany na cześć niemieckiego słowa, ponieważ w momencie jego wynalezienia (chyba około 1920 r.) międzynarodowym językiem matematyki był niemiecki. Poza tym ' t nawet zdalnie nie ma nic wspólnego ze złożonością.
• @J ö rg: Tak, ale nie ' t to po prostu Ordnung , które według niemieckiego artykułu wiki jest źródłem: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel czy mógłbyś wprowadzić niewielką zmianę w swoim artykule, abym mógł zagłosować na Ciebie? Naprawdę masz rację. Musisz dokonać edycji, zanim będę mógł głosować.
• @Jonathan, ' Nie jestem pewien, jakiej drobnej zmiany chcesz. Czy możesz po prostu przejść dalej i wprowadzić żądaną edycję? Albo możemy po prostu pozostawić odpowiedź back2dos ', wygląda na to, że i tak mógł uzyskać najlepszą odpowiedź dzięki świetnym badaniom 🙂
• Hm , ciekawy. W Szwecji Big Oh jest zwykle nazywane ” ordo ” (łac., No, order) zamiast ” ordning ” (szwedzkie słowo oznaczające porządek).

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

Cytując fragment artykułu:
Wielkie greckie litery

Wielkie O jest często naduż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 algorytm ma wartość O (n log n), istnieje stała c taka, że górna granica to cn log n.

Θ (n log n) (Big Theta) jest ściślejszy 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 najbardziej powszechne, a Big O jest najbardziej wspólne dla wszystkich. Takie rozróżnienie jest zazwyczaj nieistotne, ale warto o tym pamiętać. Właściwa notacja to w końcu poprawna notacja.

Co to jest Wielkie O?

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

Czym nie jest duże O?

Duże O nie jest testem wydajności algorytmu. Jest również pojęciowy lub abstrakcyjny, ponieważ ma tendencję do ignorowania innych czynników. Złożoność algorytmu sortowania zwykle sprowadza się do liczby sortowanych elementów, które są kluczowym czynnikiem. To jest w porządku, ale nie bierze pod uwagę takich kwestii, 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: może się zdarzyć, że porównywanie elementów jest naprawdę drogie, co potencjalnie zmieni każde porównanie algorytmów w świecie rzeczywistym; Koszt przenoszenia elementów: kopiowanie elementów jest zazwyczaj tanie, ale niekoniecznie tak jest; itp.

Komentarze

• Proste łącze do artykułu nie jest ' zbyt pomocne. ' Zwykle dobrym pomysłem jest parafrazowanie lub zacytowanie sekcji, która jest szczególnie istotna dla danego wątku.
• Czy głosy przeciwne są naprawdę konieczne? Artykuł, który podlinkował, jest bardzo istotny, a IMHO całkiem pomocny.Tymczasem najczęściej głosowaną odpowiedzią jest link do artykułu w Wikipedii. +1, aby zrównoważyć hipokryzję umysłu roju.
• -1, ponieważ artykuł, choć jest bardzo ładnym i dobrze napisanym artykułem, nie ' nie mam nic wspólnego z tym pytaniem.
• @Jorg, nigdy nie powiedziałem, że artykuł rozwiąże problem, ale podzieliłem się nim, ponieważ uznałem go za przydatny, gdy patrzyłem na te koncepcje.
• @topgun_ivard: Więc co się stanie, jeśli zmieni się w martwy link? Parafrazowanie pozwala 1) odbiorcom tego wątku otrzymać wersję Twojego linku z notatek Colesa (czas to pieniądz) oraz 2) gwarantuje, że Twój post nie stanie się nieistotny w przypadku martwego linku.

EDYCJA: Okazuje się, że się mylę. Niemniej jednak, może to pomaga komuś w utrzymaniu prostych symboli, więc nie zamierzam tego usuwać.

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

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

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

To wszystko. Nie ma w tym żadnego prawdziwego znaczenia, to tylko gra słów, jeśli will, aby pomóc Ci zapamiętać semantykę bardziej e asily.

Komentarze

• Chociaż bardzo chciałbym uwierzyć w twoją mnemoniczną propozycję (to naprawdę fajny pomysł), będę musiał zobaczyć jakiś dowód, że taki jest prawdziwy pierwotny zamiar Bachmanna. Podaj to, a ja ' daję Ci +1.
• @Jonathan Henson: Najwyraźniej prof. Knuth wprowadził mnie w błąd 🙂

„f (x) to big-oh z g (x)”

To jest matematyczny sposób przewidywania wzrostu funkcji.

Niech f i g będą funkcjami ze 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.

Można to odczytać jako „f (x) jest duże-oh z g (x)”

Duże-O jest czasami nazywane symbolem Landaua po niemiecki matematyk Edmund Landau. Nie sądzę, żeby oznaczało cokolwiek poza tym. Masz również podobne notacje duże-Omega i duże-Theta. Symbole są tak samo dowolne, jak zawsze używanie theta do oznaczania kątów w twoich trójkątach było w twojej licealnej geometrii płaskiej class.

Korekta @ back2dos dostarczyło zadowalającego wyjaśnienia O jako odnoszącej się do zamówienia. Job. Zobacz jego odpowiedź.

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

Jeśli chcesz znaleźć powód użycia notacji, przeczytaj

„Analytische Zahlentheorie” Paula Bachmanna z 1892 roku

AKTUALIZACJA: Próba uporządkowania mojej odpowiedzi i uzyskania dokładniejszej

Notacja z dużym O jest sposobem na scharakteryzowanie funkcji na podstawie współczynników wzrostu. oznacza porządek (pierwszy rząd to n, drugi rząd to n-kwadrat itp.). A jeśli nie błędnie byłby to najgorszy scenariusz dla środowiska wykonawczego (lub pamięci) metod z uwzględnieniem N elementów. Im większa kolejność, tym gorzej wykonuje 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 oznaczałoby O (N), ponieważ musisz dotrzeć do końca listy, zanim będziesz mógł dodać element itp.

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

Komentarze

• -1, ponieważ jest to po prostu stare niepoprawne ORAZ odpowiedziałem na inne pytanie niż zostało zadane. Pytanie brzmiało, dlaczego litera ” O ” jest używana, a nie ” jak duża Czy notacja O działa? „. ' mylisz się co do tego, jak działa Big-oh, chociaż … pętla w tablicy to O (n), gdzie n to rozmiar tablicy, a nie O (1) . Notacja nie ma nic wspólnego z ” cyklami ” algorytmu … to ' jest miarą górnej granicy czasu działania algorytmu.
• Nie po to, żeby się z tobą spierać, ale to ' to rodzaj tego, co miałem na myśli. Co oznacza czas pracy, prawda?Cóż, czas pracy zależy od tego, co ma zostać przetworzone na maszynie. Myślę, że w pewnym sensie używam tutaj cyklu swobodnie. Myślę, że cyklicznie powinienem był powiedzieć iteracja lub coś w tym stylu. Masz jednak rację co do górnej granicy, nie określa ona średniej. Dlatego akceptuję obniżenie wersji.