"O" velké a "o" malé

"O" velké a "o" malé ( a ) jsou matematické zápisy pro porovnávání asymptotického chování (asymptotiky) funkcí . Používají se v různých odvětvích matematiky, ale nejaktivněji - v matematické analýze , teorii čísel a kombinatorice , stejně jako v informatice a teorii algoritmů . Asymptotika je chápána jako povaha změny funkce, protože její argument směřuje k určitému bodu. $Ó$ $Ó$

$z)$ , " o malé z " znamená "nekonečně malé vzhledem k " [1] , zanedbatelné při zvažování . Význam termínu "Big O" závisí na oblasti jeho použití, ale vždy neroste rychleji než (přesné definice jsou uvedeny níže). $F$ $F$ $F$ $Z)$ $F$

Zejména:

fráze " složitost algoritmu je " znamená, že se zvýšením parametru charakterizujícího množství vstupních informací algoritmu se doba běhu algoritmu nezvýší rychleji, než se vynásobí nějakou konstantou; $O(f(n))$ $n$ $f(n)$
fráze "funkce je" o "malá funkce v blízkosti bodu " znamená, že jak se přibližuje k , klesá rychleji než (poměr směřuje k nule). $f(x)$ $g(x)$ $p$ $X$ $p$ $f(x)$ $g(x)$ $\left |f(x)\vpravo |/\left |g(x)\vpravo |$

Definice

Dovolit a být dvě funkce definované v některých proražených okolí bodu , a v tomto okolí nezmizí. Říká se, že: $f(x)$ $g(x)$ $x_{0}$ $G$

$F$ je "O" větší než when , pokud existuje taková konstanta , že pro všechny z nějakého okolí bodu platí nerovnost $G$ $x\do x_0$ $C>0$ $X$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$F$ je "o" malé z na , pokud pro nějaký existuje tak proražené okolí bodu , že nerovnost platí pro všechny $G$ $x\do x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\in U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Jinými slovy, v prvním případě je poměr v blízkosti bodu (to znamená, že je ohraničen shora) a ve druhém případě má tendenci k nule v . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\do x_0$

Označení

Obvykle se výraz " je velký ( malý) z " zapisuje pomocí rovnosti (respektive ). $F$ $Ó$ $Ó$ $G$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Tento zápis je velmi pohodlný, ale vyžaduje určitou opatrnost při jeho používání (a proto se mu lze v nejzákladnějších učebnicích vyhnout). Faktem je, že se nejedná o rovnost v obvyklém smyslu, ale o asymetrický vztah .

Zejména lze psát

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

(nebo ),

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

ale výrazy

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

(nebo )

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

bezvýznamný.

Další příklad: pokud je to pravda $x\rightarrow 0$

O(x^2) = o(x)

ale

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

Neboť jakékoli x je pravdivé

o(x) = O(x)

to znamená, že nekonečně malé množství je ohraničené, ale

O(x)\neq o(x).

Místo rovnítka by bylo metodologicky správnější používat znaky příslušnosti a inkluze, chápání a jako označení pro množiny funkcí, tedy používat zápis ve tvaru $Ó({\,})$ $Ó({\,})$

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

nebo

\mathop O(x^2)\podmnožina o(x)

místo, resp.

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

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

V praxi je však takový záznam extrémně vzácný, hlavně v těch nejjednodušších případech.

Při použití těchto zápisů musí být výslovně uvedeno (nebo z kontextu zřejmé), o která okolí (jednostranná nebo oboustranná; obsahující celá, reálná, komplexní nebo jiná čísla) a o jaké přípustné množiny funkcí se jedná (protože stejné zápis se používá ve vztahu k funkcím více proměnných, k funkcím komplexní proměnné, k maticím atd.).

Další podobná označení

Následující zápis se používá pro funkce a pro : $f(n)$ $g(n)$ $n \ až n_0$

Označení	Intuitivní vysvětlení	Definice
$f(n)\in O(g(n))$	$F$ je shora omezena funkcí (až do konstantního činitele) asymptoticky $G$	$\exists (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\in \Omega (g(n))$	$F$ je zdola omezena funkcí (až do konstantního faktoru) asymptoticky $G$	$\exists (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$F$ ohraničený zdola i shora funkcí asymptoticky $G$	$\exists (C>0), (C'>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\| \leq C'\|g(n)\|$
$f(n)\in o(g(n))$	$G$ dominuje asymptoticky $F$	$\forall (C>0) ,\existuje U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\in \omega (g(n))$	$F$ dominuje asymptoticky $G$	$\forall (C>0) ,\existuje U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$F$ je ekvivalentní asymptoticky $G$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

kde je proražené okolí bodu . $U$ $n_{0}$

Základní vlastnosti

Tranzitivita

${\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))&\implikuje &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\implikuje &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\implikuje &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\implies &f(n)=\omega (h(n))\end{matrix}}$

Reflexivita

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

Symetrie

$f(n)=\Theta(g(n)) \Šipka doleva g(n)=\Theta(f(n))$

Permutační symetrie

$\begin{matice} f(n)= O(g(n)) & \Šipka doleva & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Šipka doleva & g(n)=\omega(f(n)) \end{matrix}$

Ostatní

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

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

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

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

a v důsledku toho

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)

Asymptotický zápis v rovnicích

Pokud pravá strana rovnice obsahuje pouze asymptotický zápis (například ), pak rovnítko označuje příslušnost k množině ( ). $n=O(n^{2})$ $n\in O(n^{2})$
Pokud se asymptotický zápis vyskytuje v rovnici v jiné situaci, považuje se za substituční některé funkce. Například jako x → 0 vzorec znamená, že , kde je funkce, o které je známo pouze to, že patří do množiny . Předpokládá se, že takových funkcí je ve výrazu tolik, kolik je v něm asymptotických zápisů. Například - obsahuje pouze jednu funkci z . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $vůl)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Pokud se asymptotický zápis vyskytuje na levé straně rovnice, použije se následující pravidlo:
jakoukoli funkci zvolíme (podle předchozího pravidla) místo asymptotického zápisu na levé straně rovnice, můžeme zvolit funkce místo asymptotický zápis (podle předchozího pravidla) na pravé straně tak, aby rovnice byla správná .
Záznam například znamená, že pro jakoukoli funkci existuje nějaká funkce , takže výraz je pravdivý pro všechny . $x+o(x)=O(x)$ $f(x)\in o(x)$ $g(x)\in O(x)$ $x+f(x)=g(x)$ $X$
Některé z těchto rovnic lze spojit do řetězců. Každá z rovnic by v tomto případě měla být interpretována v souladu s předchozím pravidlem.
Například: . Všimněte si, že takový výklad implikuje naplnění vztahu . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

Výše uvedený výklad implikuje naplnění vztahu:

\vlevo, odjet. \begin{matice}A = B \\ B = C \end{matrix} \right\} \Šipka doprava A = C

, kde A , B , C jsou výrazy, které mohou obsahovat asymptotický zápis.

Příklady použití

$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})$ v . $x\rightarrow 0$

$n = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ at (vyplývá ze Stirlingova vzorce ) $n \rightarrow \infty$

$T(n)=(n+1)^2=O(n^2)$ v . $n \rightarrow \infty$

Když je nerovnost splněna . Takže dáme .

n>1

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

n_0=1, c=4

Všimněte si, že nemůžeme dát , protože , a proto je tato hodnota větší než , pro jakoukoli konstantu .

n_{0}=0

T(0)=1

C

c \cdot 0^2=0

Funkce pro má určitý stupeň růstu . $T(n)=3n^3+2n^2$ $n \rightarrow \infty$ $O(n^{3})$

Abychom to ukázali, musíme vložit a . Dá se samozřejmě říci, že to má řád , ale toto je slabší tvrzení než toto .

n_{0}=0

c=5

T(n)

O(n^{4})

T(n) = O(n^3)

Dokažme, že funkce for nemůže mít pořadí . $3^n$ $n \rightarrow \infty$ $O(2^n)$

Předpokládejme, že existují konstanty a takové, že nerovnost platí pro všechny .

C

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Pak pro všechny . Ale nabývá jakékoli hodnoty, libovolně velké, pro dostatečně velké , takže neexistuje žádná taková konstanta , která by mohla být větší pro všechny velké z některých .

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 \šipka doprava \infty$ .

Pro kontrolu stačí dát . Pak pro .

c=1

T(n) \geq cn^3

n=0, 1, ...

Historie

Zápis „O“ je velký, zavedl jej německý matematik Paul Bachmann ve druhém díle své knihy „Analytische Zahlentheorie“ (Analytická teorie čísel), vydané v roce 1894 . Zápis "o malý" byl poprvé použit dalším německým matematikem Edmundem Landauem v roce 1909 ; popularizace obou označení souvisí i s pracemi posledně jmenovaných, v souvislosti s nimiž se jim také říká Landauovy symboly . Označení pochází z německého slova „Ordnung“ (řád) [2] .

Viz také

infinitezimální

Poznámky

↑ Shvedov I. A. Kompaktní kurz matematické analýzy. Část 1. Funkce jedné proměnné. - Novosibirsk, 2003. - S. 43.
↑ D.E. Knuth. Velký Omicron a velká Omega a velká Theta : Článek . - ACM Sigact News, 1976. - V. 8 , č. 2 . - S. 18-24 . Archivováno z originálu 15. srpna 2016.

Literatura

D. Green, D. Knuth. Matematické metody pro analýzu algoritmů. — Per. z angličtiny. — M .: Mir, 1987. — 120 s.
J. McConnell. Základy moderních algoritmů. - Ed. 2 další - M .: Technosfera, 2004. - 368 s. — ISBN 5-94836-005-9 .
John E. Savage. Složitost výpočtů. - M. : Factorial, 1998. - 368 s. — ISBN 5-88688-039-9 .
V. N. Krupský. Úvod do výpočetní složitosti. - M. : Factorial Press, 2006. - 128 s. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmy a složitosti .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitola 3. Růst funkcí // Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M .: Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolský. Vyšší matematika, svazek 2.
Dionysis Zindros. Úvod do analýzy složitosti algoritmů (2012). Získáno 11. října 2013. Archivováno z originálu 10. října 2013. (Ruština)