"O" iso ja "o" pieni

"O" iso ja "o" pieni ( ja ) ovat matemaattisia merkintöjä funktioiden asymptoottisen käyttäytymisen (asymptoottisuuden) vertailuun . Niitä käytetään matematiikan eri aloilla, mutta aktiivisimmin - matemaattisessa analyysissä , lukuteoriassa ja kombinatoriikassa sekä tietojenkäsittelytieteessä ja algoritmien teoriassa . Asymptotiikka ymmärretään funktion muutoksen luonteena, koska sen argumentti pyrkii tiettyyn pisteeseen. $O$ $o$

$o(f)$ , " o small of " tarkoittaa "äärettömän pientä suhteessa " [1] , merkityksetöntä ajatellen . Termin "Big O" merkitys riippuu sen käyttöalueesta, mutta ei aina kasva nopeammin kuin (tarkat määritelmät annetaan alla). $f$ $f$ $f$ $O(f)$ $f$

Erityisesti:

ilmaus " algoritmin monimutkaisuus on " tarkoittaa, että algoritmin syöteinformaation määrää kuvaavan parametrin kasvaessa algoritmin ajoaika ei kasva nopeammin kuin kerrottuna jollain vakiolla; $O(f(n))$ $n$ $f(n)$
ilmaus "funktio on" o "pieni funktiosta pisteen läheisyydessä " tarkoittaa, että kun k:ta lähestytään , se pienenee nopeammin kuin (suhde pyrkii nollaan). $f(x)$ $g(x)$ $s$ $x$ $s$ $f(x)$ $g(x)$ $\vasen |f(x)\oikea |/\vasen |g(x)\oikea |$

Määritelmät

Antaa ja olla kaksi funktiota, jotka on määritelty jossain pisteen pisteytetyssä naapurustossa , ja tässä naapurustossa ei häviä. He sanovat että: $f(x)$ $g(x)$ $x_{0}$ $g$

$f$ on "O" suurempi kuin milloin , jos on sellainen vakio , että kaikille jostain pisteen lähialueesta epäyhtälö pätee $g$ $x\to x_0$ $C>0$ $x$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$f$ on "o" pieni arvosta at , jos jollakin on niin pisteytetty pisteen alue , että epätasa-arvo koskee kaikkia $g$ $x\to x_0$ $\varepsilon > 0$ $U_{x_0}'$ $x_{0}$ $x\in U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Toisin sanoen ensimmäisessä tapauksessa suhde on pisteen läheisyydessä (eli se on rajoitettu ylhäältä), ja toisessa tapauksessa se pyrkii nollaan pisteessä . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\to x_0$

Nimitys

Yleensä lauseke " on suuri ( pieni) " kirjoitetaan käyttämällä yhtälöä (vastaavasti ). $f$ $O$ $o$ $g$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Tämä merkintä on erittäin kätevä, mutta vaatii jonkin verran huolellisuutta sen käytössä (ja siksi sitä voidaan välttää alkeellisimmissa oppikirjoissa). Tosiasia on, että tämä ei ole tasa-arvo tavallisessa merkityksessä, vaan epäsymmetrinen suhde .

Etenkin voi kirjoittaa

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

(tai ),

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

vaan ilmaisuja

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

(tai )

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

merkityksetön.

Toinen esimerkki: jos se on totta $x\nuoli oikealle 0$

O(x^2) = o(x)

mutta

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

Mikä tahansa x on totta

o(x) = O(x)

eli äärettömän pieni määrä on rajoitettu, mutta

O(x)\neq o(x).

Yhtäläisyysmerkin sijasta olisi metodologisesti oikeampaa käyttää funktiojoukkojen nimityksinä jäsen- ja inkluusiomerkkejä, ymmärrystä ja eli merkintää muodossa. $O({\,})$ $o({\,})$

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

tai

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

sen sijaan, vastaavasti

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

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

Käytännössä tällainen tietue on kuitenkin erittäin harvinainen, lähinnä yksinkertaisimmissa tapauksissa.

Näitä merkintöjä käytettäessä on nimenomaisesti sanottava (tai kontekstista ilmeistä), mitkä lähialueet (yksi- tai kaksipuoleiset; sisältävät kokonaisluku-, reaali-, kompleksi- tai muita lukuja) ja mitkä hyväksytyt funktiojoukot ovat kyseessä (koska samat) merkintää käytetään suhteessa useiden muuttujien funktioihin, kompleksisen muuttujan funktioihin, matriiseihin jne.).

Muut samankaltaiset nimitykset

Seuraavaa merkintää käytetään funktioille ja : $f(n)$ $g(n)$ $n \ - n_0$

Nimitys	Intuitiivinen selitys	Määritelmä
$f(n)\in O(g(n))$	$f$ ylhäältä rajoittuu funktiolla (vakiotekijään asti) asymptoottisesti $g$	$\exists (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\in \Omega (g(n))$	$f$ on alhaalta rajattu funktiolla (vakiotekijään asti) asymptoottisesti $g$	$\exists (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$f$ funktion rajoittama alhaalta ja ylhäältä asymptoottisesti $g$	$\olemassa (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$ hallitsee asymptoottisesti $f$	$\forall (C>0) ,\exists U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\in \omega (g(n))$	$f$ hallitsee asymptoottisesti $g$	$\forall (C>0) ,\exists U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$f$ vastaa asymptoottisesti $g$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

missä on pisteen puhjennut ympäristö . $U$ $n_{0}$

Perusominaisuudet

Transitiivisuus

${\begin{matrix}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implys &f(n)=\Theta (h( n))\\f(n)=O(g(n))\maa g(n)=O(h(n))&\merkitsee &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\tarkoittaa &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\tarkoittaa &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\impliks &f(n)=\omega (h(n))\end{matriisi}}$

Reflexiivisyys

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

Symmetria

$f(n)=\Theta(g(n)) \nuoli vasemmalle oikealle g(n)=\Theta(f(n))$

Permutaatiosymmetria

$\begin{matrix} f(n)= O(g(n)) & \nuoli vasemmalle & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Vasen oikea nuoli & g(n)=\omega(f(n)) \end{matrix}$

Muut

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

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

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

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

ja sen seurauksena

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)

Asymptoottinen merkintä yhtälöissä

Jos yhtälön oikealla puolella on vain asymptoottinen merkintä (esimerkiksi ), yhtälömerkki ilmaisee joukon jäsenyyttä ( ). $n=O(n^{2})$ $n\in O(n^{2})$
Jos asymptoottinen merkintä esiintyy yhtälössä toisessa tilanteessa, niitä käsitellään korvaavina joitain funktioita. Esimerkiksi muodossa x → 0 kaava tarkoittaa, että , jossa on funktio, jonka tiedetään vain kuuluvan joukkoon . Oletetaan, että lausekkeessa on yhtä monta tällaista funktiota kuin siinä on asymptoottisia merkintöjä. Esimerkiksi - sisältää vain yhden funktion . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $härkä)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Jos asymptoottinen merkintätapa esiintyy yhtälön vasemmalla puolella, käytetään seuraavaa sääntöä:
mitä tahansa funktioita valitsemme (edellisen säännön mukaan) yhtälön vasemmalla puolella olevan asymptoottisen merkinnän sijaan, voimme valita funktioita asymptoottinen merkintä (edellisen säännön mukaan) oikealla puolella niin, että yhtälö on oikea .
Esimerkiksi merkintä tarkoittaa, että mille tahansa funktiolle on jokin funktio , jolloin lauseke on tosi kaikille . $x+o(x)=O(x)$ $f(x)\in o(x)$ $g(x)\in O(x)$ $x+f(x)=g(x)$ $x$
Useita näistä yhtälöistä voidaan yhdistää ketjuiksi. Jokainen yhtälö on tässä tapauksessa tulkittava edellisen säännön mukaisesti.
Esimerkiksi: . Huomaa, että tällainen tulkinta merkitsee suhteen täyttymistä . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

Yllä oleva tulkinta merkitsee suhteen täyttymistä:

\vasen. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Rightarrow A = C

, jossa A , B , C ovat lausekkeita, jotka voivat sisältää asymptoottista merkintää.

Käyttöesimerkkejä

$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})$ osoitteessa . $x\nuoli oikealle 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\oikea)$ osoitteessa (seuraa Stirlingin kaavaa ) $n \rightarrow \infty$

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

Kun eriarvoisuus täyttyy . Joten laitetaan .

n>1

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

n_0=1, c=4

Huomaa, että emme voi laittaa , koska ja siksi tämä arvo on suurempi kuin , millekään vakiolle .

n_{0}=0

T(0) = 1

c

c \cdot 0^2=0

-funktiolla on jonkin verran kasvua . $T(n) = 3n^3+2n^2$ $n \rightarrow \infty$ $O(n^{3})$

Tämän osoittamiseksi meidän on asetettava ja . Voidaan tietysti sanoa, että sillä on järjestys , mutta tämä on sitä heikompi lausunto .

n_{0}=0

c = 5

T(n)

O(n^{4})

T(n) = O(n^3)

Osoittakaamme, että funktiolla ei voi olla järjestystä . $3^n$ $n \rightarrow \infty$ $O(2^n)$

Oletetaan, että on olemassa vakioita ja sellaisia, että epäyhtälö pätee kaikkiin .

c

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Siis kaikille . Mutta se saa minkä tahansa arvon, mielivaltaisen suuren, riittävän suurelle , joten ei ole olemassa sellaista vakiota , joka voisi suurentaa kaikki suuret joistakin .

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 \oikea nuoli \infty$ .

Tarkistaaksesi, laita . Sitten varten .

c = 1

T(n) \geq cn^3

n = 0, 1, ...

Historia

Merkintä "O" on suuri, ja sen esitti saksalainen matemaatikko Paul Bachmann vuonna 1894 julkaistun kirjansa "Analytische Zahlentheorie" (Analyyttinen lukuteoria) toisessa osassa . Merkintä "o small" käytti ensimmäisen kerran toinen saksalainen matemaatikko Edmund Landau vuonna 1909 ; molempien nimitysten popularisointi liittyy myös jälkimmäisen teoksiin, joiden yhteydessä niitä kutsutaan myös Landau-symboleiksi . Nimitys tulee saksan sanasta "Ordnung" (järjestys) [2] .

Katso myös

äärettömän pieni

Muistiinpanot

↑ Shvedov I. A. Matemaattisen analyysin kompakti kurssi. Osa 1. Yhden muuttujan funktiot. - Novosibirsk, 2003. - S. 43.
↑ D.E. Knuth. Iso Omicron ja iso Omega ja iso Theta : Artikkeli . - ACM Sigact News, 1976. - V. 8 , nro 2 . - S. 18-24 . Arkistoitu alkuperäisestä 15. elokuuta 2016.

Kirjallisuus

D. Green, D. Knuth. Matemaattiset menetelmät algoritmien analysointiin. — Per. englannista. - M .: Mir, 1987. - 120 s.
J. McConnell. Nykyaikaisten algoritmien perusteet. - Toim. 2 ylimääräistä - M . : Technosfera, 2004. - 368 s. — ISBN 5-94836-005-9 .
John E. Savage. Laskelmien monimutkaisuus. - M . : Factorial, 1998. - 368 s. — ISBN 5-88688-039-9 .
V. N. Krupsky. Johdatus laskennan monimutkaisuuteen. - M . : Factorial Press, 2006. - 128 s. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmit ja monimutkaisuudet .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Luku 3. Funktioiden kasvu // Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolsky. Korkeampi matematiikka, osa 2.
Dionysis Zindros. Johdatus algoritmien kompleksisuusanalyysiin (2012). Haettu 11. lokakuuta 2013. Arkistoitu alkuperäisestä 10. lokakuuta 2013. (Venäjän kieli)