"O" nagy és "o" kicsi

Az "O" nagy és az "o" kicsi ( és ) matematikai jelölések a függvények aszimptotikus viselkedésének (aszimptotikumának) összehasonlítására . A matematika különböző ágaiban használják őket, de legaktívabban a matematikai elemzésben , a számelméletben és a kombinatorikában , valamint a számítástechnikában és az algoritmusok elméletében . Az aszimptotika alatt egy függvény változásának természetét értjük , mivel argumentuma egy bizonyos pontra hajlik. $O$ $o$

$nak,-nek)$ , " o small of " azt jelenti, hogy "végtelenül kicsi a " [1] -hez képest , figyelembe véve elhanyagolható . A "Big O" kifejezés jelentése alkalmazási területétől függ, de mindig nem növekszik gyorsabban, mint (a pontos definíciókat alább adjuk meg). $f$ $f$ $f$ $Nak,-nek)$ $f$

Különösen:

az " algoritmus összetettsége " kifejezés azt jelenti, hogy az algoritmus bemeneti információinak mennyiségét jellemző paraméter növekedésével az algoritmus futási ideje nem növekszik gyorsabban, mint valamely állandóval megszorozva; $O(f(n))$ $n$ $f(n)$
a "függvény " o "kicsi a pont közelében lévő függvényből " kifejezés azt jelenti, hogy a k-hoz közelítve gyorsabban csökken, mint ( az arány nullára hajlamos). $f(x)$ $g(x)$ $p$ $x$ $p$ $f(x)$ $g(x)$ $\left |f(x)\right |/\left |g(x)\right |$

Definíciók

Legyen és legyen két függvény, amely a pont valamely kiszúrt környezetében van definiálva , és ebben a szomszédságban nem tűnik el. Azt mondják: $f(x)$ $g(x)$ $x_{0}$ $g$

$f$ "O" nagyobb, mint amikor , ha van olyan állandó , hogy a pont valamelyik környékéről az egyenlőtlenség mindenre érvényes $g$ $x\–x_0$ $C>0$ $x$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$f$ "o" kicsi az at -ből , ha van olyan pont szomszédsága , hogy az egyenlőtlenség mindenre érvényes $g$ $x\–x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\in U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Vagyis az első esetben az arány a pont közelében van (vagyis felülről korlátos), a második esetben pedig nullára hajlik . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\–x_0$

Megnevezés

Általában a " nagy ( kicsi) " kifejezést egyenlőség (illetve ) használatával írjuk . $f$ $O$ $o$ $g$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Ez a jelölés nagyon kényelmes, de használata során némi körültekintést igényel (és ezért a legalapvetőbb tankönyvekben elkerülhető). A helyzet az, hogy ez nem a szokásos értelemben vett egyenlőség, hanem aszimmetrikus reláció .

Különösen lehet írni

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

(vagy ),

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

hanem kifejezések

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

(vagy )

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

értelmetlen.

Egy másik példa: ha igaz az $x\jobbra nyíl 0$

O(x^2) = o(x)

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

Bármely x igaz

o(x) = O(x)

vagyis egy végtelenül kicsi mennyiség korlátos, de

O(x)\neq o(x).

Az egyenlőségjel helyett módszertanilag helyesebb lenne a tagsági és befogadási jeleket, a megértést és a függvényhalmazok jelöléseként használni, vagyis a formában lévő jelölést. $O({\,})$ $o({\,})$

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

vagy

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

helyett, ill.

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

és

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

A gyakorlatban azonban rendkívül ritka az ilyen rekord, főleg a legegyszerűbb esetekben.

E jelölések használatakor kifejezetten (vagy a szövegkörnyezetből nyilvánvalóan) meg kell adni, hogy mely szomszédságokról (egy- vagy kétoldalas; egész, valós, összetett vagy egyéb számokat tartalmazó) és milyen megengedett függvényhalmazokról van szó (mivel ugyanaz) a jelölést több változó függvényeihez, komplex változó függvényeihez, mátrixaihoz stb. használjuk.

Egyéb hasonló megnevezések

A következő jelöléseket használjuk a függvényekre és a következőkre: $f(n)$ $g(n)$ $n \ to n_0$

Kijelölés	Intuitív magyarázat	Meghatározás
$f(n)\in O(g(n))$	$f$ felülről függvény határolja (konstans tényezőig) aszimptotikusan $g$	$\exists (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\in \Omega (g(n))$	$f$ alulról egy függvény határolja (konstans tényezőig) aszimptotikusan $g$	$\exists (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$f$ alulról és felülről a függvény határolja aszimptotikusan $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$ aszimptotikusan dominál $f$	$\forall (C>0) ,\exists U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\in \omega (g(n))$	$f$ aszimptotikusan dominál $g$	$\forall (C>0) ,\exists U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$f$ aszimptotikusan egyenértékű $g$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

hol van a pont kilyukadt környéke . $U$ $n_{0}$

Alaptulajdonságok

Tranzitivitás

${\begin{mátrix}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implik: &f(n)=\Theta (h( n))\\f(n)=O(g(n))\land g(n)=O(h(n))&\azt jelenti, hogy &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\azt jelenti, hogy &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\azt jelenti, hogy &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\implikálja: &f(n)=\omega (h(n))\end{mátrix}}$

Reflexivitás

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

Szimmetria

$f(n)=\Theta(g(n)) \balra jobbra nyíl g(n)=\Theta(f(n))$

Permutációs szimmetria

$\begin{mátrix} f(n)= O(g(n)) & \balra jobbra nyíl & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Balra jobbra nyíl & g(n)=\omega(f(n)) \end{mátrix}$

Egyéb

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

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

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

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

és ennek következtében

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)

Aszimptotikus jelölés az egyenletekben

Ha az egyenlet jobb oldala csak az aszimptotikus jelölést tartalmazza (például ), akkor az egyenlőségjel a halmazhoz való tagságot jelöli ( ). $n=O(n^{2})$ $n\in O(n^{2})$
Ha az aszimptotikus jelölés egy egyenletben egy másik szituációban fordul elő, akkor azokat úgy kell kezelni, mintha bizonyos függvényeket helyettesítenének. Például, mint x → 0, a képlet azt jelenti, hogy , ahol egy olyan függvény, amelyről csak azt tudjuk, hogy a halmazhoz tartozik . Feltételezzük, hogy egy kifejezésben annyi ilyen függvény van, ahány aszimptotikus jelölés van benne. Például a - csak egy függvényt tartalmaz a . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $ökör)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Ha az aszimptotikus jelölés az egyenlet bal oldalán található, akkor a következő szabályt alkalmazzuk:
bármilyen függvényt választunk (az előző szabály szerint) az egyenlet bal oldalán lévő aszimptotikus jelölés helyett, választhatunk függvényeket az egyenlet bal oldalán található aszimptotikus jelölés helyett. aszimptotikus jelölést (az előző szabály szerint) a jobb oldalon, hogy az egyenlet helyes legyen .
Például a bejegyzés azt jelenti, hogy bármely függvényhez van olyan függvény , amelyre a kifejezés igaz mindenre . $x+o(x)=O(x)$ $f(x)\in o(x)$ $g(x)\in O(x)$ $x+f(x)=g(x)$ $x$
Ezen egyenletek közül több kombinálható láncokká. Ebben az esetben minden egyenletet az előző szabálynak megfelelően kell értelmezni.
Például: . Megjegyzendő, hogy egy ilyen értelmezés magában foglalja a reláció teljesülését . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

A fenti értelmezés az összefüggés teljesülését jelenti:

\bal. \begin{mátrix}A = B \\ B = C \end{mátrix} \jobbra\} \Jobbra A = C

, ahol A , B , C olyan kifejezések, amelyek aszimptotikus jelölést tartalmazhatnak.

Használati példák

$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})$ at . $x\jobbra nyíl 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ at ( a Stirling-képletből következik ) $n \jobbra \infty$

$T(n)=(n+1)^2=O(n^2)$ at . $n \jobbra \infty$

Amikor az egyenlőtlenség teljesül . Tehát tegyük .

n>1

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

n_0=1, c=4

Vegyük észre, hogy nem tehetjük , mivel és ezért ez az érték nagyobb, mint , egyetlen állandóra sem .

n_{0}=0

T(0)=1

c

c \cdot 0^2=0

A függvénynek van egy bizonyos mértékű növekedése . $T(n)=3n^3+2n^2$ $n \jobbra \infty$ $O(n^{3})$

Ennek bemutatásához el kell helyeznünk és . Persze lehet mondani, hogy ennek van rendje , de ez ennél gyengébb állítás .

n_{0}=0

c=5

T(n)

O(n^{4})

T(n) = O(n^3)

Bizonyítsuk be, hogy a függvénynek nem lehet sorrendje . $3^n$ $n \jobbra \infty$ $O(2^n)$

Tegyük fel, hogy vannak olyan állandók , amelyekre az egyenlőtlenség érvényes .

c

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Akkor mindenkinek . De bármilyen értéket felvesz, tetszőlegesen nagyot, ha kellően nagy , tehát nincs olyan állandó , amely egyes nagyok közül minden nagyra dörzsölhetne .

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

Az ellenőrzéshez csak tegye be . Akkor azért .

c=1

T(n) \geq cn^3

n=0, 1,...

Történelem

Az "O" jelölés nagy, amelyet Paul Bachmann német matematikus vezetett be az 1894 -ben megjelent "Analytische Zahlentheorie" (Analitikai számelmélet) című könyvének második kötetében . Az "o kicsi" jelölést először egy másik német matematikus, Edmund Landau használta 1909 -ben ; mindkét elnevezés népszerűsítése az utóbbi munkáihoz is kapcsolódik, amelyek kapcsán Landau-szimbólumoknak is nevezik őket . Az elnevezés a német "Ordnung" (rend) szóból származik [2] .

Lásd még

elenyésző

Jegyzetek

↑ Shvedov I. A. A matematikai elemzés kompakt tanfolyama. 1. rész. Egy változó függvényei. - Novoszibirszk, 2003. - S. 43.
↑ D.E. Knuth. Nagy Omicron és nagy Omega és nagy Theta : Cikk . - ACM Sigact News, 1976. - V. 8 , 2. sz . - S. 18-24 . Az eredetiből archiválva: 2016. augusztus 15.

Irodalom

D. Green, D. Knuth. Matematikai módszerek algoritmusok elemzéséhez. — Per. angolról. — M .: Mir, 1987. — 120 p.
J. McConnell. A modern algoritmusok alapjai. - Szerk. 2 további - M . : Technosfera, 2004. - 368 p. — ISBN 5-94836-005-9 .
John E. Savage. A számítások összetettsége. - M . : Factorial, 1998. - 368 p. — ISBN 5-88688-039-9 .
V. N. Krupsky. Bevezetés a számítási komplexitásba. - M . : Factorial Press, 2006. - 128 p. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmusok és bonyolultságok .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 3. fejezet. Funkciónövekedés // Algoritmusok: konstrukció és elemzés = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolsky. Felsőfokú matematika, 2. kötet.
Dionysis Zindros. Bevezetés az algoritmusok komplexitáselemzésébe (2012). Letöltve: 2013. október 11. Az eredetiből archiválva : 2013. október 10.. (Orosz)