"O" stor och "o" liten

"O" stort och "o" litet ( och ) är matematiska notationer för att jämföra det asymptotiska beteendet (asymptotiska) funktioner . De används inom olika grenar av matematiken, men mest aktivt - inom matematisk analys , talteori och kombinatorik , såväl som inom datavetenskap och teorin om algoritmer . Asymptotik förstås som karaktären av förändringen i en funktion eftersom dess argument tenderar till en viss punkt. $O$ $o$

$av)$ , " o liten av " betyder "oändligt liten med avseende på " [1] , försumbar när man överväger . Innebörden av termen "Big O" beror på dess användningsområde, men växer alltid inte snabbare än (exakta definitioner ges nedan). $f$ $f$ $f$ $Av)$ $f$

Särskilt:

frasen " algoritmens komplexitet är " betyder att med en ökning av parametern som kännetecknar mängden ingångsinformation för algoritmen, kommer algoritmens gångtid att öka inte snabbare än multiplicerat med någon konstant; $O(f(n))$ $n$ $f(n)$
frasen "funktionen är" o "liten av funktionen i närheten av punkten " betyder att när k närmar sig minskar den snabbare än (förhållandet tenderar mot noll). $f(x)$ $g(x)$ $sid$ $x$ $sid$ $f(x)$ $g(x)$ $\vänster |f(x)\höger |/\vänster |g(x)\höger |$

Definitioner

Låta och vara två funktioner definierade i någon punkterad grannskap av punkten , och i detta område försvinner inte. De säger att: $f(x)$ $g(x)$ $x_{0}$ $g$

$f$ är "O" större än när , om det finns en sådan konstant att ojämlikheten gäller för alla från någon närhet av punkten $g$ $x\till x_0$ $C>0$ $x$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$f$ är "o" liten av vid , om för någon det finns en sådan punkterad grannskap av den punkt att ojämlikheten gäller för alla $g$ $x\till x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\in U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Med andra ord, i det första fallet är förhållandet i närheten av punkten (det vill säga det är avgränsat från ovan), och i det andra fallet tenderar det att vara noll vid . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\till x_0$

Beteckning

Vanligtvis skrivs uttrycket " är stort ( litet) av " med likhet (respektive ). $f$ $O$ $o$ $g$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Denna notation är mycket bekväm, men kräver viss försiktighet vid användningen (och kan därför undvikas i de mest grundläggande läroböckerna). Faktum är att detta inte är jämlikhet i vanlig mening, utan ett asymmetriskt förhållande .

I synnerhet kan man skriva

f(x) = O(g(x))

(eller ),

f(x) = o(g(x))

men uttryck

O(g(x)) = f(x)

(eller )

o(g(x)) = f(x)

meningslös.

Ett annat exempel: om det är sant att $x\högerpil 0$

O(x^2) = o(x)

men

o(x)\neq O(x^{2})

För vilket x är sant

o(x) = O(x)

det vill säga en oändlig storhet är begränsad, men

O(x)\neq o(x).

Istället för likhetstecknet vore det metodologiskt mer korrekt att använda medlemskap och inkluderingstecken, förståelse och som beteckningar för uppsättningar funktioner, det vill säga att använda notationen i formen $O({\,})$ $o({\,})$

x^{3}+x^{2}\in O(x^{3})

eller

\mathop O(x^2)\delmängd o(x)

istället för att resp.

x^{3}+x^{2}=O(x^{3})

och

\mathop O(x^2) = o(x)

Men i praktiken är en sådan uppteckning ytterst sällsynt, främst i de enklaste fallen.

När du använder dessa beteckningar måste det uttryckligen anges (eller uppenbart från sammanhanget) vilka stadsdelar (en- eller tvåsidiga; innehållande heltal, reella, komplexa eller andra tal) och vilka tillåtna uppsättningar funktioner det är fråga om (eftersom samma notation används i relation till funktioner av flera variabler, funktioner av en komplex variabel, matriser, etc.).

Andra liknande beteckningar

Följande notation används för funktioner och för : $f(n)$ $g(n)$ $n \till n_0$

Beteckning	Intuitiv förklaring	Definition
$f(n)\in O(g(n))$	$f$ begränsas ovanifrån av en funktion (upp till en konstant faktor) asymptotiskt $g$	$\exists (C>0), U : \forall (n \i U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\i \Omega (g(n))$	$f$ begränsas underifrån av en funktion (upp till en konstant faktor) asymptotiskt $g$	$\exists (C>0), U : \forall (n \i U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\i \Theta (g(n))$	$f$ begränsas underifrån och ovan av funktionen asymptotiskt $g$	$\exists (C>0), (C'>0), U : \forall (n \i U) \; C\|g(n)\| \leq \|f(n)\| \leq C'\|g(n)\|$
$f(n)\in o(g(n))$	$g$ dominerar asymptotiskt $f$	$\forall (C>0) ,\exists U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\i \omega (g(n))$	$f$ dominerar asymptotiskt $g$	$\forall (C>0) ,\exists U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$f$ är ekvivalent asymptotiskt $g$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

var är punktens punkterade grannskap . $U$ $n_{0}$

Grundläggande egenskaper

Transitivitet

${\begin{matrix}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implies &f(n)=\Theta (h( n))\\f(n)=O(g(n))\land g(n)=O(h(n))&\implicerar &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\implicerar &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\implicerar &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\implies &f(n)=\omega (h(n))\end{matris}}$

Reflexivitet

$f(n)=\Theta(f(n))$ ; ; $f(n)=O(f(n))$ $f(n)=\Omega(f(n))$

Symmetri

$f(n)=\Theta(g(n)) \Vänsterhögerpil g(n)=\Theta(f(n))$

Permutationssymmetri

$\begin{matris} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Vänster högerpil & g(n)=\omega(f(n)) \end{matris}$

Andra

$C\cdot o(f) = o(f)$

C\cdot O(f) = O(f)

$o(C \cdot f) = o(f)$

O(C \cdot f) = O(f)

och som en konsekvens,

o(-f) = o(f)

O(-f) = O(f)

$o(f) + o(f) = o(f)$

o(f) + O(f) = O(f) + O(f) = O(f)

$O(f) \cdot O(g) = O(fg)$

o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg)

$O(O(f)) = O(f)$

o(o(f)) = o(O(f)) = O(o(f)) = o(f)

Asymptotisk notation i ekvationer

Om den högra sidan av ekvationen endast innehåller den asymptotiska notationen (till exempel ), anger likhetstecknet medlemskap i mängden ( ). $n=O(n^{2})$ $n\in O(n^{2})$
Om den asymptotiska notationen förekommer i en ekvation i en annan situation, behandlas de som att de ersätter vissa funktioner. Till exempel, som x → 0, betyder formeln att , där är en funktion som man bara vet att den tillhör mängden . Det antas att det finns lika många sådana funktioner i ett uttryck som det finns asymptotiska notationer i det. Till exempel innehåller - bara en funktion från . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $oxe)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Om den asymptotiska notationen förekommer på vänster sida av ekvationen, används följande regel:
vilka funktioner vi än väljer (enligt föregående regel) istället för den asymptotiska notationen på vänster sida av ekvationen, kan vi välja funktioner istället för asymptotisk notation (enligt föregående regel) på höger sida så att ekvationen blir korrekt .
Till exempel betyder posten att för alla funktioner finns det någon funktion så att uttrycket är sant för alla . $x+o(x)=O(x)$ $f(x)\in o(x)$ $g(x)\in O(x)$ $x+f(x)=g(x)$ $x$
Flera av dessa ekvationer kan kombineras till kedjor. Var och en av ekvationerna i detta fall bör tolkas i enlighet med föregående regel.
Till exempel: . Observera att en sådan tolkning innebär att relationen uppfylls . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

Ovanstående tolkning innebär att förhållandet uppfylls:

\vänster. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Högerpil A = C

, där A , B , C är uttryck som kan innehålla asymptotisk notation.

Användningsexempel

$e^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\ldots +{\frac {x^{n}}{n!}}+\ldots =1+x+{\frac {x^{2}}{2}}+O(x^{3})$ kl . $x\högerpil 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ at (följer av Stirlingformeln ) $n \högerpil \infty$

$T(n)=(n+1)^2=O(n^2)$ kl . $n \högerpil \infty$

När ojämlikheten är uppfylld . Så låt oss sätta .

n>1

(n+1)^2<4n^2

n_0=1, c=4

Observera att vi inte kan sätta , eftersom och därför detta värde är större än , för någon konstant .

n_{0}=0

T(0)=1

c

c \cdot 0^2=0

Funktionen för har en grad av tillväxt . $T(n)=3n^3+2n^2$ $n \högerpil \infty$ $O(n^{3})$

För att visa detta måste vi sätta och . Man kan naturligtvis säga att det har ordning , men det här är ett svagare uttalande än så .

n_{0}=0

c=5

T(n)

O(n^{4})

T(n) = O(n^3)

Låt oss bevisa att funktionen för inte kan ha ordningen . $3^n$ $n \högerpil \infty$ $O(2^n)$

Låt oss anta att det finns konstanter och sådana att ojämlikheten gäller för alla .

c

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Sedan för alla . Men det antar vilket värde som helst, godtyckligt stort, för tillräckligt stor , så det finns ingen sådan konstant som kan ha majoritet för alla stora av vissa .

c \geq \left( \frac{3}{2} \right)^n

n \geq n_0

\left( \frac{3}{2} \right)^n

n

c

\left( \frac{3}{2} \right)^n

n

n_{0}

$T(n)=n^3+2n^2 = \Omega(n^3), n \högerpil \infty$ .

För att kontrollera, lägg bara . Sedan för .

c=1

T(n) \geq cn^3

n=0, 1, ...

Historik

Notationen "O" är stor, introducerad av den tyske matematikern Paul Bachmann i den andra volymen av hans bok "Analytische Zahlentheorie" (Analytisk talteori), publicerad 1894 . Notationen "o liten" användes först av en annan tysk matematiker, Edmund Landau 1909 ; populariseringen av båda beteckningarna är också kopplad till de senares verk, i samband med vilka de också kallas Landau-symboler . Beteckningen kommer från det tyska ordet "Ordnung" (ordning) [2] .

Se även

oändligt liten

Anteckningar

↑ Shvedov I. A. Kompakt kurs av matematisk analys. Del 1. Funktioner för en variabel. - Novosibirsk, 2003. - S. 43.
↑ D.E. Knuth. Stor Omicron och stor Omega och stor Theta : Artikel . - ACM Sigact News, 1976. - V. 8 , nr 2 . - S. 18-24 . Arkiverad från originalet den 15 augusti 2016.

Litteratur

D. Green, D. Knuth. Matematiska metoder för analys av algoritmer. — Trans. från engelska. — M .: Mir, 1987. — 120 sid.
J. McConnell. Grunderna i moderna algoritmer. - Ed. 2 extra - M . : Technosfera, 2004. - 368 sid. — ISBN 5-94836-005-9 .
John E. Savage. Beräkningarnas komplexitet. - M . : Factorial, 1998. - 368 sid. — ISBN 5-88688-039-9 .
V. N. Krupsky. En introduktion till beräkningskomplexitet. - M . : Factorial Press, 2006. - 128 sid. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmer och komplexiteter .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 3. Tillväxt av funktioner // Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolsky. Högre matematik, volym 2.
Dionys Zindros. Introduktion till komplexitetsanalys av algoritmer (2012). Hämtad 11 oktober 2013. Arkiverad från originalet 10 oktober 2013. (ryska)