Изворни код странице Велико О

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

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

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

== Дефиниције ==
=== "≤" ===
[[Датотека:Landau_simboli_o_slikovit_primer.png|мини|244п|''<math>g(n)=\mathcal{O}(f(n))</math>'']]

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

:<math>\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) \}</math>

Иста дефиниција, нешто другачије написана гласи:
:<math> 0 \leq \limsup_{n\to\infty} \left | \frac{g(n)}{f(n)} \right | < \infty</math>

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

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

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

:<math>\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) \}</math>

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

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

:<math>\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) \}</math>

Уз помоћ лимеса:
:<math> 
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
</math>

=== "<" ===
<math>g = o(f) </math> значи да -{g}- асимптотски спорије расте од -{f}-. Дефинисано је тако да је <math>\frac{g(n)}{f(n)}</math> нулти ред.

:<math>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) \}</math>

:<math>
\lim_{n\to\infty} \left | \frac{g(n)}{f(n)} \right | = 0 
</math>

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

:<math>\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) \}</math>

:<math>
\lim_{n\to\infty} \left | \frac{g(n)}{f(n)} \right | = \infty
</math>

== Правила за рачунање са O нотацијом ==
* <math>c \cdot f = \mathcal{O}(f)</math> за неко <math>c \geq 0</math>
* <math>\mathcal{O}(c \cdot f) = \mathcal{O} (f)</math> за неко <math>c \geq 0</math>
* <math>c \cdot \mathcal{O}(f) = \mathcal{O} (f)</math> за неко <math>c \geq 0</math>
* <math> \mathcal{O} (\mathcal{O} (f) ) = \mathcal{O} (f)</math>
* <math> \mathcal{O} (f_1) + \mathcal{O} (f_2) + \ldots + \mathcal{O}(f_k) = \mathcal{O} (\max \{f_1, \ldots, f_l \} )</math> за неку константу <math>k</math>
* <math> \mathcal{O}(f) \cdot \mathcal{O}(g) = \mathcal{O} (f \cdot g )</math>
* <math>g=\mathcal{O}(f) \Rightarrow \mathcal{O}(f+g) = \mathcal{O}(f)</math>
* <math>\log_a n = \mathcal{O} (\log_b n)</math>, за <math>\forall a,b > 1</math>; тј. база логаритма није битна, само нек је већа од 1

== Литература ==
{{Литература|2}} -{
* {{cite book|author=Paul Bachmann|title=Die Analytische Zahlentheorie. Zahlentheorie |location= |publisher= |year= |isbn= }}. pt. 2 Leipzig: B. G. Teubner, 1894.
* {{cite book|author=Edmund Landau|title=Handbuch der Lehre von der Verteilung der Primzahlen |year=1909|url=https://archive.org/details/handbuchderlehre01landuoft|location= |publisher= |isbn= }}. 2 vols. Leipzig: B. G. Teubner, 1909.
* G. H. Hardy. ''Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond'', 1910.
* {{cite book|author=Donald Knuth |title=The Art of Computer Programming |location= |publisher= |year=1997|isbn=978-0-201-89683-1|pages=}}. Volume 1: ''Fundamental Algorithms'', Third Edition. Addison–Wesley. . Section 1.2.11: Asymptotic Representations, pp. 107-123.
* {{cite book|author=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein |title=Introduction to Algorithms |location= |publisher= |year=2001|isbn=978-0-262-03293-3|pages=}}. Second Edition. MIT Press and McGraw–Hill. . Section 3.1: Asymptotic notation, pp. 41-50.
* {{Cite book| ref=harv| last = Sipser | first = Michael |year=1997| title = Introduction to the Theory of Computation | url=https://archive.org/details/introductiontoth00sips| publisher = PWS Publishing |isbn=978-0-534-94728-6|pages=[https://archive.org/details/introductiontoth00sips/page/226 226]–228}} of section 7.1: Measuring complexity.
* Jeremy Avigad, Kevin Donnelly. ''[http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf Formalizing O notation in Isabelle/HOL]''
* Paul E. Black, [http://www.nist.gov/dads/HTML/bigOnotation.html "big-O notation"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Приступљено December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/littleOnotation.html "little-o notation"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Приступљено December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omegaCapital.html "Ω"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Приступљено December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omega.html "ω"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Приступљено December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/theta.html "Θ"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Приступљено December 16, 2006.
}- {{Литература крај}}

{{нормативна контрола}}

[[Категорија:Математичка нотација]]
[[Категорија:Математичка анализа]]
[[Категорија:Информатика]]