Велико О

Из пројекта Википедија

Ландау симболи и нотација користе се у информатици и математици за описивање асимптотских тенденција (брзина раста) функција и редова. У информатици се они посебно користе за описивање временске сложености неког алгоритма да бисмо могли да их упоредимо или израчунамо колико је тешко или "сложено" израчунавање.

Главна идеја је да се симболи " $\leq$ ", " $\geq$ ", " $=$ " и " $<$ " прилагоде за функције.

Нотацију је увео Паул Бахман у својој књизи "Analytische Zahlentheorie" написаној 1894., а постала је популарна у радовима Едмунда Ландауа.

Садржај

1 Дефиниције
- 1.1 "≤"
- 1.2 "≥"
- 1.3 " = "
- 1.4 " < "
- 1.5 " > "
2 Правила за рачунање са O нотацијом

[уреди] Дефиниције

[уреди] "≤"

$g(n)=\mathcal{O}(f(n))$

$g = \mathcal{O} (f)$ значи да $g$ асимптотски не расте брже од $f$ , а дефинисано је тако што је израз $\frac{g(n)}{f(n)}$ ограничен неком константом $c$ .

$\mathcal{O} (f) = \{g | g:\mathbb{N} \rightarrow \mathbb{R}^{+}, \exists n_0 \in \mathbb{N}, \forall n \geq n_0 : g(n) \leq c \cdot f(n) \}$

Иста дефиниција, можда мало разумљивије написана:

$0 \leq \limsup_{n\to\infty} \left | \frac{g(n)}{f(n)} \right | < \infty$

Нека нас не збуњује знак "=", он у овом случају не значи једнакост већ га је увек најбоље превести као "g је спорија или једнако брза као f". У овој нотацији се увек мисли на асимптотски случај! Што ће рећи, није битно да ли је g у неком моменту или у неком интервалу већа од f, већ увек посматрамо неки моменат у бесконачности.

Понекад се у литератури користи такође нотација $g \in \mathcal{O}(f)$ $g \subseteq \mathcal{O}(f)$

[уреди] "≥"

$g = Ω(f)$ значи да g асимптотски не расте спорије од f ( g је бржа или макар исто брза као и f), а можемо искористити претходну дефиницију да бисмо добили ову нову - $f=\mathcal{O}(g)$ ( f је спорија или у најбољем случају исто брза као g).

$\Omega (f) = \{ g | g : \mathbb{N} \rightarrow \mathbb{R}^{+}, \exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: g(n) \geq c \cdot f(n) \}$

Обичнијом формулом написано: $\liminf_{n\to\infty} \left | \frac{g(n)}{f(n)} \right | > 0$

[уреди] " $=$ "

$g = Θ(f)$ значи да f и g асимптотски гледано једнако брзо расту, а то дефинишемо користећи се поново претходним дефиницијама: $g=\mathcal{O}(f)$ и $g = Ω(f)$ , односно $\Theta (f) = \mathcal{O}(f) \cap \Omega (f)$ .

$\Theta (f) = \{ g | g: \mathbb{N} \rightarrow \mathbb{R}^+, \exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0 : \frac{1}{c} \cdot f(n) \leq g(n) \leq c \cdot f(n) \}$