"O" stor og "o" lille

"O" stor og "o" lille ( og ) er matematiske notationer til sammenligning af funktioners asymptotiske adfærd (asymptotik) . De bruges i forskellige grene af matematikken, men mest aktivt - i matematisk analyse , talteori og kombinatorik , såvel som i datalogi og teorien om algoritmer . Asymptotik forstås som arten af ændringen i en funktion, da dens argument tenderer til et vist punkt. $O$ $o$

$af)$ , " o lille af " betyder "uendelig lille i forhold til " [1] , ubetydelig, når man overvejer . Betydningen af udtrykket "Big O" afhænger af dets anvendelsesområde, men vokser altid ikke hurtigere end (nøjagtige definitioner er givet nedenfor). $f$ $f$ $f$ $Af)$ $f$

I særdeleshed:

sætningen " algoritmens kompleksitet er " betyder, at med en stigning i parameteren, der karakteriserer mængden af inputinformation fra algoritmen, vil algoritmens køretid ikke stige hurtigere end ganget med en konstant; $O(f(n))$ $n$ $f(n)$
sætningen "funktionen er" o "lille af funktionen i nærheden af punktet " betyder, at når k nærmer sig , falder den hurtigere end (forholdet har en tendens til nul). $f(x)$ $g(x)$ $s$ $x$ $s$ $f(x)$ $g(x)$ $\venstre |f(x)\højre |/\venstre |g(x)\højre |$

Definitioner

Lad og være to funktioner defineret i nogle punkteret kvarter af punktet , og i dette kvarter forsvinder ikke. De siger, at: $f(x)$ $g(x)$ $x_{0}$ $g$

$f$ er "O" større end når , hvis der er en sådan konstant , at uligheden gælder for alle fra et eller andet område af punktet $g$ $x\til x_0$ $C>0$ $x$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$f$ er "o" lille på , hvis for nogen er der et så punkteret naboskab af det punkt , at uligheden gælder for alle $g$ $x\til x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\in U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Med andre ord, i det første tilfælde er forholdet i nærheden af punktet (det vil sige, det er afgrænset ovenfra), og i det andet tilfælde har det en tendens til nul ved . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\til x_0$

Betegnelse

Normalt er udtrykket " er stort ( lille) af " skrevet ved hjælp af lighed (henholdsvis ). $f$ $O$ $o$ $g$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Denne notation er meget praktisk, men kræver en vis omhu i brugen (og kan derfor undgås i de mest elementære lærebøger). Faktum er, at der ikke er tale om lighed i almindelig forstand, men et asymmetrisk forhold .

Især kan man skrive

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

(eller ),

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

men udtryk

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

(eller )

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

meningsløs.

Et andet eksempel: hvis det er rigtigt $x\højrepil 0$

O(x^2) = o(x)

men

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

For ethvert x er sandt

o(x) = O(x)

det vil sige, at en uendelig størrelse er afgrænset, men

O(x)\neq o(x).

I stedet for lighedstegnet vil det metodisk set være mere korrekt at bruge medlemskabs- og inklusionstegn, forståelse og som betegnelser for funktionssæt, det vil sige at bruge notationen i formen. $O({\,})$ $o({\,})$

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

eller

\mathop O(x^2)\undersæt o(x)

i stedet for hhv.

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

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

Men i praksis er en sådan registrering yderst sjælden, hovedsageligt i de mest simple tilfælde.

Ved brug af disse notationer skal det udtrykkeligt angives (eller tydeligt ud fra konteksten), hvilke kvarterer (en- eller tosidet; indeholdende heltal, reelle, komplekse eller andre tal) og hvilke tilladte sæt af funktioner, der er tale om (da det samme notation bruges i forhold til funktioner af flere variable, til funktioner af en kompleks variabel, til matricer osv.).

Andre lignende betegnelser

Følgende notation bruges til funktioner og til : $f(n)$ $g(n)$ $n \ til n_0$

Betegnelse	Intuitiv forklaring	Definition
$f(n)\in O(g(n))$	$f$ er afgrænset ovenfra af en funktion (op til en konstant faktor) asymptotisk $g$	$\eksisterer (C>0), U : \forall (n \i U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\i \Omega (g(n))$	$f$ er afgrænset nedefra af en funktion (op til en konstant faktor) asymptotisk $g$	$\eksisterer (C>0), U : \forall (n \i U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\i \Theta (g(n))$	$f$ afgrænset nedefra og oven af funktionen asymptotisk $g$	$\eksisterer (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$ dominerer asymptotisk $f$	$\forall (C>0) ,\eksisterer U : \forall(n \i U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\i \omega (g(n))$	$f$ dominerer asymptotisk $g$	$\forall (C>0) ,\eksisterer U : \forall(n \i U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$f$ er ækvivalent asymptotisk $g$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

hvor er punktets punkterede naboskab . $U$ $n_{0}$

Grundlæggende egenskaber

Transitivitet

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

Refleksivitet

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

Symmetri

$f(n)=\Theta(g(n)) \venstrehøjrepil g(n)=\Theta(f(n))$

Permutationssymmetri

$\begin{matrix} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Venstrehøjrepil & g(n)=\omega(f(n)) \end{matrix}$

Andre

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

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

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

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

og som følge heraf

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 ligninger

Hvis højre side af ligningen kun indeholder den asymptotiske notation (for eksempel ), så angiver lighedstegnet medlemskab i mængden ( ). $n=O(n^{2})$ $n\in O(n^{2})$
Hvis den asymptotiske notation forekommer i en ligning i en anden situation, behandles de som at erstatte nogle funktioner for dem. For eksempel, som x → 0, betyder formlen , at , hvor er en funktion, som man kun ved, at den tilhører mængden . Det antages, at der er lige så mange sådanne funktioner i et udtryk, som der er asymptotiske notationer i det. For eksempel indeholder - kun én funktion fra . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $okse)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Hvis den asymptotiske notation forekommer i venstre side af ligningen, anvendes følgende regel:
uanset hvilke funktioner vi vælger (ifølge den foregående regel) i stedet for den asymptotiske notation i venstre side af ligningen, kan vi vælge funktioner i stedet for asymptotisk notation (ifølge den foregående regel) på højre side, så ligningen er korrekt .
Indtastningen betyder f.eks., at der for enhver funktion er en funktion , således at udtrykket er sandt for alle . $x+o(x)=O(x)$ $f(x)\in o(x)$ $g(x)\in O(x)$ $x+f(x)=g(x)$ $x$
Flere af disse ligninger kan kombineres til kæder. Hver af ligningerne i dette tilfælde skal fortolkes i overensstemmelse med den foregående regel.
For eksempel :. Bemærk, at en sådan fortolkning indebærer opfyldelsen af relationen . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

Ovenstående fortolkning indebærer opfyldelsen af forholdet:

\venstre. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Højrepil A = C

, hvor A , B , C er udtryk, der kan indeholde asymptotisk notation.

Eksempler på brug

$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øjrepil 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ at (følger af Stirling-formlen ) $n \højrepil \infty$

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

Når uligheden er opfyldt . Så lad os sætte .

n>1

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

n_0=1, c=4

Bemærk, at vi ikke kan sætte , da og derfor denne værdi er større end , for enhver konstant .

n_{0}=0

T(0)=1

c

c \cdot 0^2=0

Funktionen for har en grad af vækst . $T(n)=3n^3+2n^2$ $n \højrepil \infty$ $O(n^{3})$

For at vise dette skal vi sætte og . Man kan selvfølgelig sige, at der er orden , men det er et svagere udsagn end som så .

n_{0}=0

c=5

T(n)

O(n^{4})

T(n) = O(n^3)

Lad os bevise, at funktionen for ikke kan have rækkefølgen . $3^n$ $n \højrepil \infty$ $O(2^n)$

Lad os antage, at der er konstanter og sådan, at uligheden gælder for alle .

c

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Så for alle . Men den antager en hvilken som helst værdi, vilkårligt stor, for tilstrækkelig stor , så der er ingen sådan konstant , der kan have større betydning for alle store af nogle .

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øjrepil \infty$ .

For at tjekke skal du bare sætte . Så for .

c=1

T(n) \geq cn^3

n=0, 1, ...

Historie

Notationen "O" er stor, introduceret af den tyske matematiker Paul Bachmann i andet bind af hans bog "Analytische Zahlentheorie" (Analytisk talteori), udgivet i 1894 . Notationen "o lille" blev først brugt af en anden tysk matematiker, Edmund Landau i 1909 ; populariseringen af begge betegnelser er også forbundet med sidstnævntes værker, i forbindelse med hvilke de også kaldes Landau-symboler . Betegnelsen kommer fra det tyske ord "Ordnung" (orden) [2] .

Se også

uendelig lille

Noter

↑ Shvedov I. A. Kompakt kursus af matematisk analyse. Del 1. Funktioner af en variabel. - Novosibirsk, 2003. - S. 43.
↑ D.E. Knuth. Stor Omicron og stor Omega og stor Theta : Artikel . - ACM Sigact News, 1976. - V. 8 , nr. 2 . - S. 18-24 . Arkiveret fra originalen den 15. august 2016.

Litteratur

D. Green, D. Knuth. Matematiske metoder til analyse af algoritmer. — Trans. fra engelsk. — M .: Mir, 1987. — 120 s.
J. McConnell. Grundlæggende om moderne algoritmer. - Ed. 2 ekstra - M . : Technosfera, 2004. - 368 s. — ISBN 5-94836-005-9 .
John E. Savage. Beregningernes kompleksitet. - M . : Faktoriel, 1998. - 368 s. — ISBN 5-88688-039-9 .
V. N. Krupsky. En introduktion til beregningsmæssig kompleksitet. - M . : Factorial Press, 2006. - 128 s. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmer og kompleksiteter .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 3. Vækst af funktioner // Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Red. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolsky. Højere matematik, bind 2.
Dionysis Zindros. Introduktion til kompleksitetsanalyse af algoritmer (2012). Hentet 11. oktober 2013. Arkiveret fra originalen 10. oktober 2013. (Russisk)