Notacja dużego O

Przykład notacji Big O: ${\ Displaystyle {\ color {red} f (x)} \ in O {\ color {niebieski} (g (x))}}$ as istnieje ${\ Displaystyle M> 0}$ (np. ${\ Displaystyle M = 1}$ ) i ${\ Displaystyle x_ {0}}$ (np. ${\ Displaystyle x_ {0} = 5 }$ ) takie, że ${\ Displaystyle {\ kolor {czerwony} f (x)} \ równoważnik {\ kolor {niebieski} Mg (x)}}$ ilekroć ${\ Displaystyle x \geq x_{0}}$ .

Notacja dużego O to notacja matematyczna opisująca ograniczające zachowanie funkcji , gdy argument dąży do określonej wartości lub nieskończoności. Big O jest członkiem rodziny notacji wymyślonych przez Paula Bachmanna , Edmunda Landaua i innych, zwanych wspólnie notacją Bachmanna-Landaua lub notacją asymptotyczną . Litera O została wybrana przez Bachmanna jako Ordnung , czyli kolejność zbliżania się .

W informatyce notacja dużego O jest używana do klasyfikowania algorytmów według tego, jak rośnie ich czas działania lub zapotrzebowanie na miejsce wraz ze wzrostem rozmiaru danych wejściowych. W analitycznej teorii liczb notacja dużego O jest często używana do wyrażenia granicy różnicy między funkcją arytmetyczną a lepiej rozumianym przybliżeniem; słynnym przykładem takiej różnicy jest reszta z twierdzenia o liczbach pierwszych . Notacja Big O jest również używana w wielu innych dziedzinach, aby zapewnić podobne szacunki.

Notacja Big O charakteryzuje funkcje według ich tempa wzrostu: różne funkcje o tej samej asymptotycznej szybkości wzrostu można przedstawić za pomocą tej samej notacji O. Litera O jest używana, ponieważ tempo wzrostu funkcji jest również określane jako rząd funkcji . Opis funkcji za pomocą notacji dużego O zwykle zapewnia jedynie górną granicę tempa wzrostu funkcji.

Z notacją dużego O jest powiązanych kilka powiązanych notacji, wykorzystujących symbole o , Ω, ω i Θ do opisania innych rodzajów granic asymptotycznych stóp wzrostu.

Definicja formalna

Niech funkcja do oszacowania będzie $funkcją$$o wartościach$ rzeczywistych lub zespolonych i niech porównawcza będzie funkcją o wartościach rzeczywistych Niech obie funkcje zostaną zdefiniowane na pewnym nieograniczonym podzbiorze dodatnich liczb rzeczywistych i będą ściśle $displaystyle$ wartości $x}$ . Jeden pisze

$${\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr)} \ quad {\ tekst {jak}} x \ do \infty}$$

jeśli wartość bezwzględna $wszystkich wystarczająco$ dodatnią stałą wielokrotnością dla wartości $displaystyle$$x$ } Oznacza to, że jeśli istnieje dodatnia liczba rzeczywista, $} M$$\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr )}$ i liczbę rzeczywistą taką, że ${\ displaystyle x_ {0}}$

$${\ Displaystyle | f (x) | \ równoważnik Mg (x) \ quad {\ tekst {dla wszystkich}} x \ geq x_ {0}.}$$

W wielu kontekstach założenie, że interesuje nas stopa wzrostu, gdy zmienna dąży do nieskończoności, pozostaje niewypowiedziane i pisze się prościej, że ${\ displaystyle x}$

$${\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr)}.}$$

$\ displaystyle a = 0}$ opisania zachowania w pobliżu jakiejś liczby rzeczywistej $($$:$ ) mówimy za

$${\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr)} \ quad {\ tekst {jak}} x \ do}$$

$że$ istnieją liczby dodatnie $i$ , $dla$ wszystkich z ${\ Displaystyle 0 <| xa | <\ delta}$ ,

$${\ Displaystyle | f (x) | \ równoważnik Mg (x).}$$

Ponieważ dla takich wartości , obie te definicje można ujednolicić za pomocą granicy przełożonej , $g (x$${\ Displaystyle$ }

$${\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr)} \ quad {\ tekst {jak}} x \ do}$$

Jeśli

$${\ Displaystyle \ limsup _ {x \ do a} {\ Frac {\ lewo | f (x) \ prawo |} {g (x)} }<\ infty.}$$

I w obu tych definicjach $sol ,$$punktem$ ( niezależnie od tego, czy ) jest skupienia domen i ja $}$$infty$ . e $.$ , w każdym sąsiedztwie być nieskończenie wiele punktów wspólnych. Ponadto, $)$ wskazano w artykule o granicy niższej i granicy wyższej , (przynajmniej na osi liczb rzeczywistych zawsze istnieje.

W informatyce powszechna jest nieco bardziej restrykcyjna definicja: $\ displaystyle$ muszą być funkcjami od pewnego nieograniczonego podzbioru dodatnich liczb całkowitych do nieujemnych liczb rzeczywistych; $f}$ wtedy ${\ Displaystyle f (x) = O {\ bigl (} g (x) {\ bigr)}}$ jeśli istnieją dodatnie liczby całkowite ${\ Displaystyle M}$ i ${\ Displaystyle n_ {0}}$ takie, że ${\ Displaystyle f (n) \ równoważnik Mg (n)}$ dla wszystkich ${\ Displaystyle n \ geq n_ {0} }$ .

Przykład

W typowym użyciu notacja O jest asymptotyczna, to znaczy odnosi się do bardzo dużego x . W tej sytuacji wkład terminów, które rosną „najszybciej”, w końcu sprawi, że pozostałe staną się nieistotne. W rezultacie można zastosować następujące zasady upraszczające:

• Jeśli f ( x ) jest sumą kilku wyrazów, to jeśli jest jeden o największym tempie wzrostu, to można go zachować, a wszystkie inne pominąć.
• Jeśli f ( x ) jest iloczynem kilku czynników, to wszelkie stałe (czynniki w iloczynie, które nie zależą od x ) można pominąć.

Na przykład, niech f ( x ) = 6 x ⁴ − 2 x ³ + 5 i załóżmy, że chcemy uprościć tę funkcję, używając notacji O , aby opisać jej tempo wzrostu, gdy x dąży do nieskończoności. Ta funkcja jest sumą trzech wyrazów: 6 x ⁴ , −2 x ³ i 5 . Spośród tych trzech wyrazów, ten o najwyższym tempie wzrostu to ten, który ma największy wykładnik w funkcji x , czyli 6 x ⁴ . Teraz można zastosować drugą regułę: 6 x ⁴ to iloczyn 6 i x ⁴ , w którym pierwszy czynnik nie zależy od x . Pominięcie tego czynnika daje uproszczoną postać x ⁴ . Zatem mówimy, że f ( x ) jest „dużym O” z x ⁴ . Matematycznie możemy zapisać f ( x ) = O ( x ⁴ ) . Rachunek ten można potwierdzić za pomocą formalnej definicji: niech f ( x ) = 6 x ⁴ − 2 x ³ + 5 oraz g ( x ) = x ⁴ . Stosując formalną definicję z powyższego, stwierdzenie, że f ( x ) = O ( x ⁴ ) jest równoważne jego rozwinięciu,

$${\ Displaystyle | f (x) | \ równoważnik Mx ^ {4}}$$

dla pewnego odpowiedniego wyboru x ₀ i M oraz dla wszystkich x > x ₀ . Aby to udowodnić, niech ₀ x = 1 i M = 13 . Wtedy dla wszystkich x > x ₀ :

$${\ Displaystyle {\ rozpocząć {wyrównane} | 6x ^ {4} -2x ^ {3} + 5 | & \ równoważnik 6x ^ {4} +|2x^{3}|+5\\&\równik 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{wyrównane}}}$$

Więc

$${\ Displaystyle | 6x ^ {4} -2x ^ {3} + 5 | \ równoważnik 13x ^ {4}.}$$

Stosowanie

Notacja Big O ma dwa główne obszary zastosowań:

• W matematyce jest powszechnie używany do opisania, jak bardzo szereg skończony przybliża daną funkcję , zwłaszcza w przypadku uciętego szeregu Taylora lub rozwinięcia asymptotycznego
• W informatyce jest przydatny w analizie algorytmów

W obu zastosowaniach funkcja g ( x ) pojawiająca się w O (·) jest zwykle wybierana tak, aby była tak prosta, jak to tylko możliwe, z pominięciem stałych czynników i wyrażeń niższego rzędu.

Istnieją dwa formalnie zbliżone, ale zauważalnie różne zastosowania tej notacji:

• nieskończone asymptotyki
• nieskończenie małe asymptotyki.

To rozróżnienie ma jednak zastosowanie tylko w zastosowaniu, a nie w zasadzie - formalna definicja „wielkiego O” jest taka sama dla obu przypadków, tylko z różnymi ograniczeniami dla argumentu funkcji.

Nieskończone asymptotyki

Wykresy funkcji powszechnie używanych w analizie algorytmów, przedstawiające liczbę operacji N w funkcji wielkości wejściowej n dla każdej funkcji

Notacja dużego O jest przydatna podczas analizowania algorytmów pod kątem wydajności. Na przykład czas (lub liczba kroków) potrzebny do rozwiązania problemu o rozmiarze n może wynosić T ( n ) = 4 n ² − 2 n + 2 . W n rośnie, wyraz n ² zaczyna dominować, więc wszystkie inne wyrazy można pominąć — na przykład, gdy n = 500 , wyraz 4 n ² jest 1000 razy większy niż wyraz 2 n . Zignorowanie tego drugiego miałoby znikomy wpływ na wartość wyrażenia dla większości celów. Ponadto współczynniki stają się nieistotne, jeśli porównamy je z jakimkolwiek innym rzędem wyrażeń, takim jak wyrażenie zawierające termin n ³ lub n ⁴ . Nawet jeśli T ( n ) = 1 000 000 n ² , jeśli U ( n ) = n ³ , to drugie zawsze przekroczy pierwsze, gdy n wzrośnie powyżej 1 000 000 ( T (1 000 000) = 1 000 000 ³ = U (1 000 000) ). Ponadto liczba kroków zależy od szczegółów modelu maszyny, na której działa algorytm, ale różne typy maszyn zwykle różnią się tylko o stały współczynnik liczby kroków potrzebnych do wykonania algorytmu. Tak więc notacja dużego O oddaje to, co pozostaje: piszemy albo

${\ Displaystyle T (n) = O (n ^ {2})}$

Lub

${\ Displaystyle T (n) \ w O (n ^ {2})}$

i powiedzmy, że algorytm ma złożoność czasową rzędu n ² . Znak „ = ” nie ma wyrażać „jest równy” w normalnym sensie matematycznym, ale raczej bardziej potoczne „jest”, więc drugie wyrażenie jest czasami uważane za dokładniejsze (patrz dyskusja „Znak równości” poniżej), podczas gdy pierwszy jest uważany przez niektórych za nadużycie notacji .

Nieskończenie małe asymptotyki

Duże O może być również użyte do opisania składnika błędu w przybliżeniu do funkcji matematycznej. Najbardziej znaczące terminy są zapisywane jawnie, a następnie najmniej znaczące terminy są podsumowywane jednym dużym terminem O. Rozważmy na przykład szereg wykładniczy i dwa jego wyrażenia, które są ważne, gdy x jest małe:

${\ Displaystyle {\ rozpocząć {wyrównane} e ^ {x} & =1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!} }+\dotsb &{\text{dla wszystkich }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\ text{as }}x\do 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\do 0\end{wyrównane}}}$

Drugie wyrażenie (to z O ( x ³ )) oznacza, że ​​wartość bezwzględna błędu e ^x − (1 + x + x ² /2) jest co najwyżej pewnymi stałymi czasami | x ³ | gdy x jest wystarczająco bliskie 0.

Nieruchomości

Jeśli funkcję f można zapisać jako skończoną sumę innych funkcji, to najszybciej rosnąca wyznacza rząd f ( n ) . Na przykład,

${\ Displaystyle f (n) = 9 \ log n + 5 (\ log n) ^ {4} + 3 n ^ {2} + 2 n ^ {3} = O (n ^ {3}) \ qquad {\ tekst { as }}n\do \infty .}$

W szczególności, jeśli funkcja może być ograniczona wielomianem w n , to ponieważ n dąży do nieskończoności , można pominąć wyrazy wielomianu niższego rzędu. Zbiory O ( n ^c ) i O ( c ⁿ ) są bardzo różne. Jeśli c jest większe niż jeden, to ten ostatni rośnie znacznie szybciej. Funkcja, która rośnie szybciej niż n ^c dla dowolnego c , nazywana jest superwielomianem . Taka, która rośnie wolniej niż jakakolwiek funkcja wykładnicza postaci c ⁿ , nazywana jest subwykładniczą . Algorytm może wymagać czasu, który jest zarówno superwielomianowy, jak i podwykładniczy; przykłady tego obejmują najszybsze znane algorytmy rozkładu liczb całkowitych na czynniki i funkcję n ^{log n} .

Możemy zignorować wszelkie potęgi n wewnątrz logarytmów. Zbiór O (log n ) jest dokładnie taki sam jak O (log ( n ^c )) . Logarytmy różnią się tylko stałym współczynnikiem (ponieważ log( n ^c ) = c log n ), a zatem notacja dużego O to ignoruje. Podobnie logarytmy o różnych stałych podstawach są równoważne. Z drugiej strony wykładniki o różnych podstawach nie są tego samego rzędu. Na przykład 2 ⁿ i 3 ⁿ nie są tego samego rzędu.

Zmiana jednostek może, ale nie musi, wpływać na kolejność wynikowego algorytmu. Zmiana jednostek jest równoznaczna z pomnożeniem odpowiedniej zmiennej przez stałą, gdziekolwiek się pojawi. Na przykład, jeśli algorytm działa w kolejności n ² , zastąpienie n przez cn oznacza, że ​​algorytm działa w kolejności c ² n ² , a notacja dużego O ignoruje stałą c ² . Można to zapisać jako c ² n ² = O( n ² ) . Jeśli jednak algorytm działa w kolejności 2 ⁿ , zastąpienie n przez cn daje 2 ^cn = (2 ^c ) ⁿ . Ogólnie nie jest to równoważne 2 ^{n .} Zmiana zmiennych może również wpłynąć na kolejność wynikowego algorytmu. Na przykład, jeśli czas działania algorytmu wynosi O ( n ) , mierzony w kategoriach liczby n cyfr liczby wejściowej x , to jego czas działania wynosi O ( log x ) , mierzony jako funkcja samej liczby wejściowej x , ponieważ n = O (log x ) .

Produkt

${\ Displaystyle f_ {1} = O (g_ {1}) {\ tekst {i }}f_{2}=O(g_{2})\strzałka w prawo f_{1}f_{2}=O(g_{1}g_{2})}$

${ \displaystyle f\cdot O(g)=O(fg)}$

Suma

fa ${\ Displaystyle f_ {1} = O (g_ {1})}$ i ${\ Displaystyle f_ {2} = O (g_ {2})$ wtedy ${\ Displaystyle f_ {1} + f_ {2} = O (\ max (g_ {1}, g_ {2}))}$ . Wynika z tego, że jeśli ${\ Displaystyle f_ {1} = O (g)}$ i ${\ Displaystyle f_ {2} = O (g)}$ to ${\ Displaystyle f_ {1} + f_ {2} \ w O (g)}$ . Innymi słowy, to drugie $mówi$ wypukłym stożkiem .

Mnożenie przez stałą

Niech k będzie niezerową stałą. $) = O (g)}$ g . Innymi słowy, jeśli ${\ Displaystyle f = O (g)}$ , to ${\ Displaystyle k \ cdot f = O (g).}$

Wiele zmiennych

Duże O (i małe o, Ω itd.) mogą być również używane z wieloma zmiennymi. Aby formalnie zdefiniować duże O dla wielu zmiennych, załóżmy, $funkcjami$$}$ są dwiema zdefiniowanymi na pewnym podzbiorze $^ {n}}$ . Mówimy

${\ Displaystyle f (\ mathbf {x}) {\ tekst {jest}} O (g (\ mathbf {x}}} \ quad {\ tekst { jako }}\mathbf {x} \do \infty }$

$,$ gdy istnieją stałe $,$ takie że ${\ Displaystyle | f (\ mathbf {x}) | \ równoważnik C | g (\ mathbf {x}) |}$ dla wszystkich ${\ Displaystyle \ mathbf {x}}$ z ${\ Displaystyle x_ {i }\geq M}$ dla pewnego ${\ Displaystyle i.}$$\$$Displaystyle$ warunek, że dla pewnego $można$ zapisać $|$ gdzie oznacza normę Czebyszewa . Na przykład oświadczenie

${\ Displaystyle f (n, m) = n ^ {2} + m ^ {3} + O (n +m)\quad {\text{ as }}n,m\to \infty}$

twierdzi, że istnieją stałe C i M takie, że

${\ Displaystyle | f (n, m) - (n ^ {2} + m ^ {3}) | \ równoważnik C | n + m |}$

zachodzi albo ${\ displaystyle m \ geq M}$ lub ${\ displaystyle n \ geq M} .$ Ta definicja pozwala wszystkim współrzędnym $.$ się do nieskończoności W szczególności oświadczenie

${\ Displaystyle f (n, m) = O (n ^ {m}) \ quad {\ tekst {jak}} n, m \ do \infty}$

(tj. ${\ Displaystyle \ istnieje C \, \ istnieje M \, \ forall n \, \ forall m \, \ cdots}$ )

${\ Displaystyle \ forall m \ dwukropek ~ f (n, m) = O (n ^ {m}) \ quad {\ tekst {jak }}n\do \infty}$

(tj. ${\ Displaystyle \ forall m \ \ istnieje C \ \ istnieje M \ \ forall n \ \ cdots} )$ .

Zgodnie z tą definicją podzbiór, na którym zdefiniowana jest funkcja, jest istotny przy uogólnianiu stwierdzeń z ustawienia jednowymiarowego na ustawienie wielowymiarowe. Na przykład, jeśli ${\ Displaystyle f (n, m) = 1}$ i ${\ Displaystyle g (n, m) = n}$ , to $n, m) = O (g (n, m)}}$ ( jeśli ograniczymy ${\ Displaystyle f}$ i ${\ Displaystyle g}$${\ Displaystyle [1, \ infty) ^ {2}}$ , ale nie, jeśli są zdefiniowane na ${\ Displaystyle [0, \ infty) ^ {2}}$ .

Nie jest to jedyne uogólnienie dużego O na funkcje wielowymiarowe iw praktyce istnieje pewna niekonsekwencja w wyborze definicji.

Sprawy notacji

Znak równości

Wyrażenie „ f ( x ) to O ( g ( x ))” zgodnie z powyższą definicją jest zwykle zapisywane jako f ( x ) = O ( g ( x )) . Niektórzy uważają to za nadużycie notacji , ponieważ użycie znaku równości może wprowadzać w błąd, ponieważ sugeruje symetrię, której nie ma to stwierdzenie. Jak de Bruijn , O ( x ) = O ( x ² ) jest prawdziwe, ale O ( x ² ) = O ( x ) nie. Knuth opisuje takie twierdzenia jako „jednokierunkowe równości”, ponieważ gdyby strony można było odwrócić, „moglibyśmy wydedukować śmieszne rzeczy, takie jak n = n ² z tożsamości n = O ( n ² ) i n ² = O ( n ² ) ”. W innym liście Knuth zwrócił również uwagę, że „znak równości nie jest symetryczny w stosunku do takich zapisów”, ponieważ w tym zapisie „matematycy zwykle używają znaku =, tak jak używają słowa„ jest ”w języku angielskim: Arystoteles jest człowiek, ale człowiek niekoniecznie jest Arystotelesem”.

Z tych powodów bardziej precyzyjne byłoby użycie notacji zbiorczej i zapisanie f ( x ) ∈ O ( g ( x )) (czytane jako: „ f ( x ) jest elementem O ( g ( x ))”, lub " f ( x ) jest w zbiorze O ( g ( x ))"), myśląc o O ( g ( x )) jako o klasie wszystkich funkcji h ( x ) takich, że | godz ( x )| ≤ C g ( x ) dla pewnej stałej C . Jednak użycie znaku równości jest zwyczajowe.

Inne operatory arytmetyczne

Notacja dużego O może być również używana w połączeniu z innymi operatorami arytmetycznymi w bardziej skomplikowanych równaniach. Na przykład h ( x ) + O ( f ( x )) oznacza zbiór funkcji o wzroście h ( x ) plus część, której wzrost jest ograniczony do wzrostu f ( x ). Zatem,

${\ Displaystyle g (x) = h (x) + O (f (x))}$

wyraża to samo co

${\ Displaystyle g (x) -h (x) = O (f (x)).}$

Przykład

Załóżmy, że opracowywany jest algorytm do działania na zbiorze n elementów. Jego twórcy są zainteresowani znalezieniem funkcji T ( n ), która wyrazi, jak długo zajmie wykonanie algorytmu (w pewnym arbitralnym pomiarze czasu) pod względem liczby elementów w zbiorze wejściowym. Algorytm działa, najpierw wywołując podprogram w celu posortowania elementów w zbiorze, a następnie wykonując własne operacje. Sortowanie ma znaną złożoność czasową O ( n ² ), a po wykonaniu podprogramu algorytm musi wykonać dodatkowe 55 n ³ + 2 n + 10 kroków, zanim się zakończy. Zatem całkowitą złożoność ( n ) = 55n3 + O ( n2 ^{) .} czasową algorytmu można wyrazić jako T Tutaj terminy 2 n + 10 są podciągnięte do szybciej rosnącego O ( n ² ). Ponownie, to użycie pomija niektóre formalne znaczenie symbolu „=”, ale pozwala na użycie notacji dużego O jako rodzaju wygodnego symbolu zastępczego.

Wiele zastosowań

W bardziej skomplikowanym użyciu O (·) może występować w różnych miejscach równania, nawet kilka razy z każdej strony. Na przykład następujące są prawdziwe dla ${\ displaystyle n \ do \ infty}$ :

$${\ Displaystyle {\ rozpocząć {wyrównane} (n + 1) ^ {2} & = n ^ {2} + O (n), \\ (n + O (n ^ {1/2})) \ cdot ( n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n }).\end{wyrównane}}}$$

Znaczenie takich stwierdzeń jest następujące: dla dowolnych funkcji, które spełniają każde O (·) po lewej stronie, istnieją pewne funkcje spełniające każde O (·) po prawej stronie, takie, że podstawienie wszystkich tych funkcji do równania daje dwie strony równe. Na przykład trzecie równanie powyżej oznacza: „Dla dowolnej funkcji f ( n ) = O (1) istnieje pewna funkcja g ( n ) = O ( e ⁿ ) taka, że ​​n ^{f ( n )} = g ( n ). " Jeśli chodzi o powyższą „notację zestawu”, oznacza to, że klasa funkcji reprezentowana przez lewą stronę jest podzbiorem klasy funkcji reprezentowanej przez prawą stronę. W tym zastosowaniu „=” jest formalnym symbolem, który w przeciwieństwie do zwykłego użycia „=” nie jest relacją symetryczną . Zatem na przykład n ^{O (1)} = O ( e ⁿ ) nie implikuje fałszywego stwierdzenia O ( e ⁿ ) = n ^{O (1)} .

Skład

Duże O jest pisane jako wielka litera „O” pisana kursywą, jak w poniższym przykładzie: ${\ Displaystyle O (n ^ {2})}$ . W TeX-u tworzy się go po prostu wpisując O w trybie matematycznym. W przeciwieństwie do notacji Bachmanna-Landaua o greckiej nazwie, nie potrzebuje specjalnego symbolu. Jednak niektórzy autorzy używają zamiast $wariantu kaligraficznego.$

Rzędy wspólnych funkcji

Dalsze informacje: Złożoność czasowa § Tabela typowych złożoności czasowych

Oto lista klas funkcji, które są powszechnie spotykane podczas analizowania czasu działania algorytmu. W każdym przypadku c jest stałą dodatnią, a n rośnie bez ograniczeń. Wolniej rosnące funkcje są zwykle wymienione jako pierwsze.

Notacja	Nazwa	Przykład
${\ Displaystyle O (1)}$	stały	Określanie, czy liczba binarna jest parzysta czy nieparzysta; Obliczanie ${\ Displaystyle (-1) ^ {n}}$ ; Korzystanie z tabeli wyszukiwania o stałym rozmiarze
${\ Displaystyle O (\ log \ log n)}$	podwójny logarytm	Średnia liczba porównań zużytych na znalezienie elementu przy użyciu wyszukiwania interpolacyjnego w posortowanej tablicy równomiernie rozłożonych wartości
${\ Displaystyle O (\ log n)}$	logarytmiczny	Znajdowanie elementu w posortowanej tablicy za pomocą wyszukiwania binarnego lub zrównoważonego drzewa wyszukiwania oraz wszystkich operacji na stercie dwumianowej
${\ Displaystyle O ((\ log n) ^ {c})}$${\ textstyle c> 1}$	polilogarytmiczny	Kolejność łańcuchów macierzowych można rozwiązać w czasie polilogarytmicznym na równoległej maszynie o swobodnym dostępie .
${\ Displaystyle O (n ^ {c})}$${\ textstyle 0 <c <1}$	potęga ułamkowa	Wyszukiwanie w drzewie kd
${\ Displaystyle O (n)}$	liniowy	Znalezienie elementu na nieposortowanej liście lub w nieposortowanej tablicy; dodanie dwóch n -bitowych liczb całkowitych metodą ripple carry
${\ Displaystyle O (n \ log ^ {*} n)}$	n gwiazda logarytmiczna n	Wykonywanie triangulacji prostego wielokąta za pomocą algorytmu Seidela lub algorytmu Union-Find . Zauważ, że ${\ Displaystyle \ log ^ {*} (n) = {\ rozpocząć {przypadki} 0 ,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{przypadki}}}$
${\ Displaystyle O (n \ log n) = O (\ log n!)}$	liniowo , logliniowo, quasiliniowo lub „ n log n ”	Wykonywanie szybkiej transformaty Fouriera ; najszybsze możliwe sortowanie porównawcze ; sortowanie na stosie i sortowanie przez scalanie
${\ Displaystyle O (n ^ {2})}$	kwadratowy	Mnożenie dwóch liczb n -cyfrowych przez mnożenie podręcznikowe ; proste algorytmy sortowania, takie jak sortowanie bąbelkowe , sortowanie przez wybieranie i sortowanie przez wstawianie ; (najgorszy przypadek) związany z niektórymi zwykle szybszymi algorytmami sortowania, takimi jak quicksort , Shellsort i tree sort
${\ Displaystyle O (n ^ {c})}$	wielomianowy lub algebraiczny	gramatyki przylegającej do drzewa ; maksymalne dopasowanie dla grafów dwudzielnych ; znalezienie wyznacznika z dekompozycją LU
${\ Displaystyle L_ {n} [\ alfa, c] = e ^ { (c + o (1)) (\ ln n) ^ {\ alfa} (\ ln \ ln n) ^ {1- \ alfa}}} < α < 1 {\ textstyle 0 <$$}$	Notacja L lub podwykładnicza	Rozkładanie liczby na czynniki za pomocą sita kwadratowego lub sita pól liczbowych
${\ Displaystyle O (c ^ {n})}$${\ textstyle c> 1}$	wykładniczy	Znalezienie (dokładnego) rozwiązania problemu komiwojażera za pomocą programowania dynamicznego ; określenie, czy dwie instrukcje logiczne są równoważne przy użyciu wyszukiwania siłowego
${\ Displaystyle O (n!)}$	silnia	Rozwiązanie problemu komiwojażera za pomocą wyszukiwania metodą brute-force; generowanie wszystkich nieograniczonych permutacji posetu ; znalezienie wyznacznika z rozwinięciem Laplace'a ; wyliczanie wszystkich partycji zestawu

fa ${\ Displaystyle f (n) = O (n!)}$ jest czasami osłabiane do ${\ Displaystyle f (n) = O$ w celu wyprowadzenia prostszych wzorów na złożoność asymptotyczną. ${\ Displaystyle k> 0}$ i do $\ Displaystyle c> 0}$ , ${\ Displaystyle O (n ^ {c} (\ log n) ^ { k})}$$varepsilon$ więc podzbiorem $})}$ dla dowolnego można go uznać za wielomian z jakieś większe zamówienie.

Powiązane notacje asymptotyczne

Big O jest szeroko stosowane w informatyce. Wraz z kilkoma innymi pokrewnymi notacjami tworzy rodzinę notacji Bachmanna-Landaua.

Notacja Little-o

„Małe o” przekierowuje tutaj. Dla bejsbolisty zobacz Omara Vizquela .

Intuicyjnie stwierdzenie „ f ( x ) to o ( g ( x )) ” (czytaj „ f ( x ) to niewiele o g ( x ) ”) oznacza, że ​​g ( x ) rośnie znacznie szybciej niż f ( x ) . Tak jak poprzednio, niech f będzie funkcją o wartościach rzeczywistych lub zespolonych, a g funkcją o wartościach rzeczywistych, obie zdefiniowane na pewnym nieograniczonym podzbiorze dodatnich liczb rzeczywistych , tak że g ( x ) jest ściśle dodatnie dla wszystkich wystarczająco dużych wartości x . Jeden pisze

${\ Displaystyle f (x) = o (g (x)} \ quad {\ tekst {jak}} x \ do \ infty}$

jeśli dla każdej dodatniej stałej ε istnieje stała taka, że ${\ displaystyle x_ {0}}$

${\ Displaystyle | f (x) | \ równoważnik \ varepsilon g (x) \ quad {\ tekst {dla wszystkich}} x \ geq x_ {0}.}$

Na przykład jeden ma

${\ Displaystyle 2x = o (x ^ {2})}$ i ${\ Displaystyle 1/x = o (1)}$ oba jako ${\ displaystyle x \ do \ infty.}$

Różnica między definicją notacji dużego-O a definicją małego-o polega na tym, że podczas gdy ta pierwsza musi być prawdziwa dla co najmniej jednej stałej M , druga musi być spełniona dla każdej dodatniej stałej ε , jakkolwiek małej. W ten sposób notacja little-o jest silniejszym stwierdzeniem niż odpowiadająca jej notacja big-O: każda funkcja, która jest małym-o z g, jest również dużym-O z g , ale nie każda funkcja, która jest dużym-O z g, jest również mało-o z g . Na przykład ${\ Displaystyle 2x ^ {2} = O (x ^ {2})}$ ale ${\ Displaystyle 2x ^ {2} \ neq o(x^{2})}$ .

Ponieważ g ( x ) jest niezerowe lub przynajmniej staje się niezerowe poza pewnym punktem, relacja jest równoważna ${\ Displaystyle f (x) = o (g (x))}$ Do

${\ Displaystyle \ lim _ {x \ do \ infty}} {\ Frac {f (x)}} {g (x)}} = 0} (i to jest$ w fakt, jak Landau pierwotnie zdefiniował notację little-o).

Little-o respektuje szereg operacji arytmetycznych. Na przykład,

jeśli c jest niezerową stałą i $\ Displaystyle f = o (g)}$${\ Displaystyle c \ cdot f = o (g)}$ to do , a

jeśli ${\ Displaystyle f = o (F)}$ i ${\ Displaystyle g = o (G)}$ wtedy ${\ Displaystyle f \ cdot g = o (F \ cdot G).}$

Spełnia również relację przechodniości :

jeśli ${\ Displaystyle f = o (g)}$ i ${\ Displaystyle g = o (h)}$ wtedy ${\ displaystyle f = o (h).}$

Notacja Big Omega

$omega$ zapisem jest , czytane jako „duża ”. Istnieją dwie szeroko rozpowszechnione i niezgodne definicje tego stwierdzenia

${\ Displaystyle f (x) = \ Omega (g (x))}$ jak ${\ Displaystyle x \ do a}$ ,

gdzie a jest pewną liczbą rzeczywistą, ∞ lub −∞, gdzie f i g są funkcjami rzeczywistymi zdefiniowanymi w sąsiedztwie a , i gdzie g jest dodatnie w tym sąsiedztwie.

Definicja Hardy'ego-Littlewooda jest używana głównie w analitycznej teorii liczb , a definicja Knutha głównie w teorii złożoności obliczeniowej ; definicje nie są równoważne.

Definicja Hardy'ego-Littlewooda

W 1914 roku Godfrey Harold Hardy i John Edensor Littlewood wprowadzili nowy symbol , który jest zdefiniowany w następujący sposób: ${\ Displaystyle \ Omega}$

${\ Displaystyle f (x) = \ Omega (g (x))}$ as ${\ Displaystyle x \ do \ infty}$ jeśli ${\ Displaystyle \ limsup _ {x \ do \ infty} \ lewo | {\ Frac {f (x)} {g (x)}} \ prawej|> 0.}$

Tak więc ${\ Displaystyle f (x) = \ Omega (g (x))}$ jest negacją ${\ Displaystyle f (x)=o(g(x))}$ .

$Displaystyle \ Omega _ {R}}$ ci sami autorzy wprowadzili dwa nowe symbole i , jako: ${\$

${\ Displaystyle f (x) = \ Omega _ {R} (g (x))}$ as ${\ Displaystyle x \ do \ infty}$ jeśli ${\ Displaystyle \ limsup _ {x \ do \ infty} {\ Frac {f (x)}} {g (x)}}> 0}$ ;

${\ Displaystyle f (x) = \ Omega _ {L} (g (x))}$ jak ${\ Displaystyle x \ do \ infty}$ jeśli ${\ Displaystyle \ liminf _ {x \ do \ infty} {\ Frac {f (x)} {g (x)} <0.}$

Tych symboli użył Edmund Landau w tym samym znaczeniu w 1924 r. Po Landau notacja nigdy nie była ponownie używana dokładnie w ten sposób; ${\ Displaystyle \ Omega _ {R}}$ stał się ${\ Displaystyle \ Omega _ {+}}$ i stał się ${\ Displaystyle \ Omega _ {L}}$${\ Displaystyle \ Omega _ {-} }$ .

Te trzy symbole ${\ Displaystyle \ Omega, \ Omega _ {+}, \ Omega _ {-}}$ , a także ${\ Displaystyle f (x) = \ Omega _ {\ pm} (g (x))}$ (co oznacza, że ${\ Displaystyle f (x) = \ Omega _ {+} ( g (x))}$ i ${\ Displaystyle f (x) = \ Omega _ {-} (g (x))}$ są teraz spełnione), są obecnie używane w analitycznej teorii liczb .

Proste przykłady

Mamy

${\ Displaystyle \ sin x = \ Omega (1)}$ jak ${\ Displaystyle x \ do \ infty,}$

a dokładniej

${\ Displaystyle \ sin x = \ Omega _ {\ pm} (1)}$ jako ${\ displaystyle x \ do \ infty.}$

Mamy

${\ Displaystyle \ sin x + 1 = \ Omega (1)}$ jako ${\ Displaystyle x \ do \ infty,}$

a dokładniej

${\ Displaystyle \ sin x + 1 = \ omega _ {+} (1)}$ jako ${\ displaystyle x \ do \ infty;}$

Jednakże

${\ Displaystyle \ sin x + 1 \ nie = \ Omega _ {-} (1)}$ jako ${\ displaystyle x \ do \ infty.}$

Definicja Knutha

W 1976 roku Donald Knuth opublikował artykuł uzasadniający użycie symbolu $do$ opisania silniejszej właściwości. Knuth napisał: „Dla wszystkich zastosowań, które widziałem do tej pory w informatyce, silniejszy wymóg… jest znacznie bardziej odpowiedni”. Zdefiniował

${\ Displaystyle f (x) = \ Omega (g (x)) \ strzałka w lewo g (x) = O ( f(x))}$

z komentarzem: „Chociaż zmieniłem definicję Hardy'ego i Littlewooda $czuję$ się usprawiedliwiony, ponieważ ich definicja nie jest w żadnym wypadku w powszechnym użyciu i ponieważ istnieją inne sposoby, aby powiedzieć, czego chcą powiedzieć w stosunkowo rzadkich przypadkach, gdy ich definicja ma zastosowanie”.

Rodzina notacji Bachmanna-Landaua

Notacja	Nazwa	Opis	Definicja formalna	Definicja limitu
${\ Displaystyle f (n) = o (g (n))}$	Małe O; Mały O	f jest zdominowane przez g asymptotycznie	${\ Displaystyle \ forall k> 0 \ \ istnieje n_ {0} \, \ forall n> n_ {0} \ dwukropek | f (n) | <k \, g (n)}$	${\ Displaystyle \ lim _ {n \ do \ infty} {\ Frac {f (n)}} {g (n)}} = 0}$
${\ Displaystyle f (n) = O (g (n))}$	duże O; duży och; Wielki Omikron	${\ displaystyle | f |}$ jest asymptotycznie ograniczony powyżej przez g (do stałego współczynnika).	${\ Displaystyle \ istnieje k> 0 \, \ istnieje n_ {0} \, \ forall n> n_ {0} \ dwukropek | f (n) | \ równoważnik k \, g (n)}$	${\ Displaystyle \ limsup _ {n \ do \ infty}} {\ Frac {f (n)}} {g (n)}} <\ infty}$
${\ Displaystyle f (n) = \ Theta (g (n))}$	Wielka Teta	f jest ograniczona zarówno powyżej, jak i poniżej przez g asymptotycznie	${\ Displaystyle \ istnieje k_ {1}> 0 \, \ istnieje k_ {2}> 0 \, \ istnieje n_ {0} \, \ dla wszystkich n> n_ {0} \ dwukropek}$${\ Displaystyle k_ {1} \ g (n) \ równoważnik f (n) \ równoważnik k_ {2} \,g(n)}$	${\ Displaystyle f (n) = O (g (n))}$ i ${\ Displaystyle f (n) = \ Omega (g(n))}$ (wersja Knutha)
${\ Displaystyle f (n) \ sim g (n)}$	Z rozkazu	f jest równe g asymptotycznie	${\ Displaystyle \ forall \ varepsilon > 0 \, \ istnieje n_ {0} \, \ forall n> n_ {0} \ dwukropek \ lewo | {\ Frac {f (n)}} {g (n)}} -1\prawo|<\varepsilon }$	${\ Displaystyle \ lim _ {n \ do \ infty} {\ Frac {f (n)}} {g (n)}} = 1}$
${\ Displaystyle f (n) = \ omega (g (n))}$	Big Omega w teorii złożoności (Knuth)	f jest od dołu ograniczone przez g asymptotycznie	${\ Displaystyle \ istnieje k> 0 \ \ istnieje n_ {0} \ \ forall n> n_ {0} \ dwukropek f ( n)\geq k\,g(n)}$	${\ Displaystyle \ liminf _ {n \ do \ infty} {\ Frac {f (n)}} {g (n)}}> 0}$
${\ Displaystyle f (n) = \ omega (g (n))}$	Mała Omega	f dominuje g asymptotycznie	${\ Displaystyle \ forall k> 0 \ \ istnieje n_ {0} \, \ forall n> n_ {0} \ dwukropek f ( n)>k\,g(n)}$	${\ Displaystyle \ lim _ {n \ do \ infty}} {\ Frac {f (n)}} {g (n)}} = \ infty}$
${\ Displaystyle f (n) = \ omega (g (n))}$	Big Omega w teorii liczb (Hardy – Littlewood)	${\ displaystyle | f |}$ nie jest zdominowany przez g asymptotycznie	${\ Displaystyle \ istnieje k> 0 \ \ forall n_ {0} \, \ istnieje n> n_ {0} \ dwukropek | f (n) | \ geq k \, g (n)}$	${\ Displaystyle \ limsup _ {n \ do \ infty} {\ Frac {\ lewo | f (n) \ prawo |} {g (n)}}> 0}$

Definicje granic zakładają, że są wystarczająco duże. $} Tabela jest (częściowo) posortowana od najmniejszej$$displaystyle g (n)> 0$ \ $omega$$wersja$ tym sensie, że ) $Displaystyle \$$_$$_$ odpowiada _ Jednak wersja Littlewood $.$ odpowiada żadnemu takiemu opisowi)

Informatyka wykorzystuje duże ${\ Displaystyle O}$ , duże Theta ${\$ małe $Displaystyle O}$ , małe omega ${\ Displaystyle \ omega}$ i duże Omegi Knutha ${\ Displaystyle \ Omega}$ notacje. Analityczna teoria $liczb$ często wykorzystuje dużą Hardy'ego-Littlewooda (z ${$ +, - lub ± lub bez) i $∼$$styl wyświetlania \sim }$$Displaystyle$ O notacje. Mała notacja omega $nie$ używana tak często w analizie.

Zastosowanie w informatyce

Dalsze informacje: Analiza algorytmów

Nieformalnie, zwłaszcza w informatyce, notacja dużego O często może być używana nieco inaczej do opisania asymptotycznego ścisłego powiązania, gdzie użycie notacji dużego Theta Θ może być bardziej odpowiednie w danym kontekście. Na przykład, rozważając funkcję T ( n ) = 73 n ³ + 22 n ² + 58, wszystkie poniższe są ogólnie akceptowalne, ale ściślejsze granice (takie jak liczby 2 i 3 poniżej) są zwykle zdecydowanie preferowane przez luźniejsze granice (takie jak numer 1 poniżej).

1. T ( n ) = O ( n ¹⁰⁰ )
2. T ( n ) = O ( n ³ )
3. T ( n ) = Θ ( n ³ )

Odpowiednikami angielskich stwierdzeń są odpowiednio:

1. T ( n ) rośnie asymptotycznie nie szybciej niż n ¹⁰⁰
2. T ( n ) rośnie asymptotycznie nie szybciej niż n ³
3. T ( n ) rośnie asymptotycznie tak szybko jak n ³ .

Tak więc, chociaż wszystkie trzy stwierdzenia są prawdziwe, każde z nich zawiera coraz więcej informacji. Jednak w niektórych dziedzinach notacja dużego O (numer 2 na powyższych listach) byłaby używana częściej niż notacja big Theta (pozycje o numerze 3 na powyższych listach). Na przykład, jeśli T ( n ) reprezentuje czas działania nowo opracowanego algorytmu dla wielkości wejściowej n , wynalazcy i użytkownicy algorytmu mogą być bardziej skłonni do wyznaczenia górnej asymptotycznej granicy czasu, jaki zajmie wykonanie tego algorytmu bez wykonywania wyraźne stwierdzenie o dolnej asymptotycznej granicy.

Inna notacja

W swojej książce „Wprowadzenie do algorytmów ” Cormen , Leiserson , Rivest i Stein rozważają zbiór funkcji f , które spełniają

${\ Displaystyle f (n) = O (g (n)) \ quad (n \ do \ infty) ~.}$

W poprawnej notacji zbiór ten można na przykład nazwać O ( g ), gdzie

$${\ Displaystyle O (g) = \ {f: {\ tekst {istnieją stałe dodatnie}} ~ c ~ {\ tekst {i}} ~ n_ {0} ~ {\ tekst {takie, że}} ~ 0 \ równoważnik f(n)\leq cg(n){\text{dla wszystkich}}n\geq n_{0}\}.}$$

Autorzy twierdzą, że użycie operatora równości (=) do oznaczenia przynależności do zbioru zamiast operatora przynależności do zbioru (∈) jest nadużyciem notacji, ale ma to zalety. Wewnątrz równania lub nierówności użycie notacji asymptotycznej oznacza anonimową funkcję w zbiorze O ( g ), która eliminuje wyrażenia niższego rzędu i pomaga zmniejszyć nieistotny bałagan w równaniach, na przykład:

${\ Displaystyle 2n ^ {2} + 3n + 1 = 2n ^ {2} + O (n).}$

Rozszerzenia notacji Bachmanna-Landaua

  Innym zapisem używanym czasami w informatyce jest Õ (czytaj miękkie-O ): f ( n ) = Õ ( g ( n )) jest skrótem dla f ( n ) = O ( g ( n ) log ^k n ) dla pewnego k . Niektórzy autorzy piszą O ^* w tym samym celu. Zasadniczo jest to notacja dużego O, ignorująca czynniki logarytmiczne, ponieważ efekty szybkości wzrostu niektórych innych funkcji superlogarytmicznych wskazują na eksplozję szybkości wzrostu dla parametrów wejściowych o dużych rozmiarach, która jest ważniejsza dla przewidywania złej wydajności w czasie wykonywania niż dokładniejsze -efekty punktowe wnoszone przez logarytmiczny czynnik(i) wzrostu. Notacja ta jest często używana, aby uniknąć „wychwytywania nitek” w ramach tempa wzrostu, które są określane jako zbyt ściśle ograniczone dla rozpatrywanych spraw (ponieważ log k n ^wynosi zawsze o ( n ε ⁾ dla dowolnej stałej k i dowolnego ε > 0 ).

Również notacja L , zdefiniowana jako

${\ Displaystyle L_ {n} [\ alfa, c] = e ^ { (c+o(1))(\ln n)^{\alpha}(\ln \ln n)^{1-\alpha}}}$

jest wygodny dla funkcji, które są między wielomianem a wykładnikiem pod względem . ${\ displaystyle \ ln n}$ .

Uogólnienia i powiązane zastosowania

Uogólnienie na funkcje przyjmujące wartości w dowolnej znormalizowanej przestrzeni wektorowej jest proste (zastąpienie wartości bezwzględnych normami), gdzie f i g nie muszą przyjmować wartości w tej samej przestrzeni. Możliwe jest również uogólnienie na funkcje g przyjmujące wartości w dowolnej grupie topologicznej . „Proces ograniczania” x → xo można również uogólnić wprowadzając dowolną podstawę filtru , czyli do sieci _skierowanych f i g . Notacja o może służyć do definiowania pochodnych i różniczkowalności w dość ogólnych przestrzeniach, a także (asymptotycznej) równoważności funkcji,

${\ Displaystyle f \ sim g \ iff (fg) \ w o (g)}$

która jest relacją równoważności i pojęciem bardziej restrykcyjnym niż relacja „ f to Θ ( g )” z góry. (Redukuje się do lim f / g = 1, jeśli f i g są dodatnimi funkcjami o wartościach rzeczywistych.) Na przykład 2 x to Θ ( x ), ale 2 x - x nie jest o ( x ).

Historia (notacje Bachmanna-Landaua, Hardy'ego i Vinogradova)

Symbol O został po raz pierwszy wprowadzony przez teoretyka liczb Paula Bachmanna w 1894 roku w drugim tomie jego książki Analytische Zahlentheorie („ analityczna teoria liczb ”). Przyjął to teoretyk liczb Edmund Landau iw ten sposób zainspirował się do wprowadzenia w 1909 r. Notacji o; stąd oba są teraz nazywane symbolami Landaua. Notacje te były używane w matematyce stosowanej w latach pięćdziesiątych XX wieku do analizy asymptotycznej. Symbol (w znaczeniu „nie jest o ” $) został wprowadzony w 1914$ przez Hardy'ego i Littlewooda. Hardy i Littlewood wprowadzili również w 1916 ${\ Displaystyle \ Omega _ {R}$ symbole („prawo” $)$ i („lewo”), prekursory współczesnych symboli ${\ Displaystyle \ Omega _ {+}}$ („nie jest mniejsze niż małe o”) i ${\ Displaystyle \ Omega _ {-}}$ („nie jest większe niż małe o”). Dlatego symbole Omega (z ich oryginalnym znaczeniem) są czasami określane jako „symbole Landau”. Ten zapis $.$ się powszechnie używany w teorii liczb co najmniej od lat pięćdziesiątych XX wieku W latach siedemdziesiątych wielkie O zostało spopularyzowane w informatyce przez Donalda Knutha , który wprowadził powiązaną notację Theta i zaproponował inną definicję notacji Omega.

Landau nigdy nie używał dużych symboli Theta i małych symboli Omega.

Symbole Hardy'ego były (według współczesnej notacji O )

${\ Displaystyle f \ preccurlyeq g \ iff f \ w O (g)}$ i ${\ Displaystyle f \ prec g \ iff f \ w o (g);}$

$nie zdefiniował ani$$.$ użył notacji , ani , jak to donoszono) Hardy wprowadził symbole $I$ a $) w swoim traktacie „Orders of Infinity” z 1910 r.$ wykorzystał je tylko w trzech artykułach (1910–1913 ). W swoich prawie 400 pozostałych artykułach i książkach konsekwentnie używał symboli Landau O i O.

Notacja Hardy'ego nie jest już używana. Z drugiej strony, w latach trzydziestych XX wieku rosyjski teoretyk liczb Iwan Matwiejewicz Winogradow $notacji$ swoją $.$ , która jest coraz częściej stosowana w teorii liczb zamiast Mamy

${\ Displaystyle f \ ll g \ iff f \ w O (g),}$

i często oba zapisy są używane w tym samym artykule.

Big-O pierwotnie oznacza „zakon” („Ordnung”, Bachmann 1894), a zatem jest literą łacińską. Ani Bachmann, ani Landau nigdy nie nazywają go „Omicron”. Symbol został znacznie później (1976) postrzegany przez Knutha jako duży omikron , prawdopodobnie w odniesieniu do jego definicji symbolu Omega . Nie należy używać cyfry zero .

Zobacz też

• Rozwinięcie asymptotyczne : Aproksymacja funkcji uogólniających wzór Taylora
• Algorytm asymptotycznie optymalny : wyrażenie często używane do opisania algorytmu, który ma asymptotycznie górną granicę w obrębie stałej dolnej granicy problemu
• Duże O w zapisie prawdopodobieństwa : O _p , o _p
• Limit gorszy i limit wyższy : wyjaśnienie niektórych zapisów granicznych użytych w tym artykule
• Twierdzenie główne (analiza algorytmów) : Do analizy rekurencyjnych algorytmów typu „dziel i zwyciężaj” przy użyciu notacji Big O
• Twierdzenie Nachbina : precyzyjna metoda ograniczania złożonych funkcji analitycznych , tak aby można było określić dziedzinę zbieżności przekształceń całkowych
• Kolejność przybliżenia
• Złożoność obliczeniowa operacji matematycznych

Dalsza lektura

• Hardy'ego, GH (1910). Zamówienia nieskończoności: „Infinitärcalcül” Paula du Bois-Reymonda . Wydawnictwo Uniwersytetu Cambridge .
•   Knuth, Donald (1997). „1.2.11: Reprezentacje asymptotyczne”. Podstawowe algorytmy . Sztuka programowania komputerowego. Tom. 1 (wyd. 3). Addison-Wesley. ISBN 978-0-201-89683-1 .
•   Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). „3.1: Notacja asymptotyczna”. Wprowadzenie do algorytmów (wyd. 2). MIT Press i McGraw-Hill. ISBN 978-0-262-03293-3 .
•   Sipser, Michael (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. s. 226 –228. ISBN 978-0-534-94728-6 .
• Awigad, Jeremy; Donnelly, Kevin (2004). Formalizacja notacji O w Isabelle / HOL (PDF) . Międzynarodowa wspólna konferencja na temat automatycznego rozumowania. doi : 10.1007/978-3-540-25984-8_27 .
• Czarny, Paul E. (11 marca 2005). Czarny, Paul E. (red.). „notacja dużego O” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
• Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „notacja małego o” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
• Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „Ω” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
• Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „ω” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
• Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). "Θ" . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .

Linki zewnętrzne

• Wzrost sekwencji — OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Wprowadzenie do notacji asymptotycznych
• Symbole Landaua
• Notacja Big-O – do czego służy
• Notacja Big O wyjaśniona prostym angielskim
• Przykład dużego O w dokładności schematu centralnej podzielonej różnicy dla pierwszej pochodnej Zarchiwizowane 2018-10-07 w Wayback Machine
• Delikatne wprowadzenie do analizy złożoności algorytmu