Велико О

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

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

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

Дефиниције[уреди | уреди извор]

"≤"[уреди | уреди извор]

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

${\displaystyle {\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)\}}$

Иста дефиниција, нешто другачије написана гласи:

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

Знак „=“ у овом случају не значи једнакост већ га је увек најбоље превести као „g је спорија или једнако брза као f“. У овој нотацији се увек мисли на асимптотски случај, односно, није битно да ли је g у неком моменту или у неком интервалу већа од f, већ посматрамо тенденцију приликом приближавања бесконачности.

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

"≥"[уреди | уреди извор]

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

${\displaystyle \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)\}}$

Исто то нешто једноставнијом формулом гласи: ${\displaystyle \liminf _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|>0}$

"="[уреди | уреди извор]

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

${\displaystyle \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)\}}$

Уз помоћ лимеса:

${\displaystyle 0<\liminf _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|\leq \limsup _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|<\infty }$

"<"[уреди | уреди извор]

${\displaystyle g=o(f)}$ значи да g асимптотски спорије расте од f. Дефинисано је тако да је ${\displaystyle {\frac {g(n)}{f(n)}}}$ нулти ред.

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

${\displaystyle \lim _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|=0}$

">"[уреди | уреди извор]

Ознака ${\displaystyle g=\omega (f)}$ значи да је g асимптотски бржа од f. Као и код ${\displaystyle \Omega (f)}$ и ${\displaystyle {\mathcal {O}}(f)}$ тако се и овде служимо супротном дефиницијом: ${\displaystyle f=o(g)}$.

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

${\displaystyle \lim _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|=\infty }$

Правила за рачунање са O нотацијом[уреди | уреди извор]

• ${\displaystyle c\cdot f={\mathcal {O}}(f)}$ за неко ${\displaystyle c\geq 0}$
• ${\displaystyle {\mathcal {O}}(c\cdot f)={\mathcal {O}}(f)}$ за неко ${\displaystyle c\geq 0}$
• ${\displaystyle c\cdot {\mathcal {O}}(f)={\mathcal {O}}(f)}$ за неко ${\displaystyle c\geq 0}$
• ${\displaystyle {\mathcal {O}}({\mathcal {O}}(f))={\mathcal {O}}(f)}$
• ${\displaystyle {\mathcal {O}}(f_{1})+{\mathcal {O}}(f_{2})+\ldots +{\mathcal {O}}(f_{k})={\mathcal {O}}(\max\{f_{1},\ldots ,f_{l}\})}$ за неку константу ${\displaystyle k}$
• ${\displaystyle {\mathcal {O}}(f)\cdot {\mathcal {O}}(g)={\mathcal {O}}(f\cdot g)}$
• ${\displaystyle g={\mathcal {O}}(f)\Rightarrow {\mathcal {O}}(f+g)={\mathcal {O}}(f)}$
• ${\displaystyle \log _{a}n={\mathcal {O}}(\log _{b}n)}$, за ${\displaystyle \forall a,b>1}$; тј. база логаритма није битна, само нек је већа од 1

Литература[уреди | уреди извор]