Veliko O

Landau simboli i notacija koriste se u informatici i matematici za opisivanje asimptotskih tendencija (brzina rasta) funkcija i redova. U informatici se oni posebno koriste za opisivanje vremenske složenosti nekog algoritma da bismo mogli da ih uporedimo ili izračunamo koliko je teško ili „složeno“ izračunavanje.

Glavna ideja je da se simboli „$\leq$“, „$\geq$“, „$=$“ i „$<$“ prilagode za funkcije.

Notaciju je uveo Paul Bahman u svojoj knjizi „Analytische Zahlentheorie“ napisanoj 1894, a postala je popularna u radovima Edmunda Landaua.

Definicije

"≤"

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

$g={\mathcal {O}}(f)$ znači da $g$ asimptotski ne raste brže od $f$, a definisano je tako što je izraz ${\frac {g(n)}{f(n)}}$ ograničen nekom konstantom $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)\}$

Ista definicija, nešto drugačije napisana glasi:

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

Znak „=“ u ovom slučaju ne znači jednakost već ga je uvek najbolje prevesti kao „g je sporija ili jednako brza kao f“. U ovoj notaciji se uvek misli na asimptotski slučaj, odnosno, nije bitno da li je g u nekom momentu ili u nekom intervalu veća od f, već posmatramo tendenciju prilikom približavanja beskonačnosti.

Ponekad se u literaturi koristi takođe notacija $g\in {\mathcal {O}}(f)$ $g\subseteq {\mathcal {O}}(f)$

"≥"

Oznaka $g=\Omega (f)$ znači da g asimptotski ne raste sporije od f (g je brža ili makar isto brza kao i f), a koristeći prethodnu definiciju se dobija ova - $f={\mathcal {O}}(g)$ (f je sporija ili u najboljem slučaju isto brza kao 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)\}$

Isto to nešto jednostavnijom formulom glasi: $\liminf _{n\to \infty }\left|{\frac {g(n)}{f(n)}}\right|>0$

"="

$g=\Theta (f)$ znači da f i g asimptotski gledano jednako brzo rastu, a to definišemo koristeći se ponovo prethodnim definicijama: $g={\mathcal {O}}(f)$ i $g=\Omega (f)$, odnosno $\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)\}$

Uz pomoć limesa:

$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$

"<"

$g=o(f)$ znači da g asimptotski sporije raste od f. Definisano je tako da je ${\frac {g(n)}{f(n)}}$ nulti red.

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

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

">"

Oznaka $g=\omega (f)$ znači da je g asimptotski brža od f. Kao i kod $\Omega (f)$ i ${\mathcal {O}}(f)$ tako se i ovde služimo suprotnom definicijom: $f=o(g)$.

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

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

Pravila za računanje sa O notacijom

• $c\cdot f={\mathcal {O}}(f)$ za neko $c\geq 0$
• ${\mathcal {O}}(c\cdot f)={\mathcal {O}}(f)$ za neko $c\geq 0$
• $c\cdot {\mathcal {O}}(f)={\mathcal {O}}(f)$ za neko $c\geq 0$
• ${\mathcal {O}}({\mathcal {O}}(f))={\mathcal {O}}(f)$
• ${\mathcal {O}}(f_{1})+{\mathcal {O}}(f_{2})+\ldots +{\mathcal {O}}(f_{k})={\mathcal {O}}(\max\{f_{1},\ldots ,f_{l}\})$ za neku konstantu $k$
• ${\mathcal {O}}(f)\cdot {\mathcal {O}}(g)={\mathcal {O}}(f\cdot g)$
• $g={\mathcal {O}}(f)\Rightarrow {\mathcal {O}}(f+g)={\mathcal {O}}(f)$
• $\log _{a}n={\mathcal {O}}(\log _{b}n)$, za $\forall a,b>1$; tj. baza logaritma nije bitna, samo nek je veća od 1

Literatura

• Paul Bachmann. Die Analytische Zahlentheorie. Zahlentheorie. pt. 2 Leipzig: B. G. Teubner, 1894.
• Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen. 2 vols. Leipzig: B. G. Teubner, 1909.
• G. H. Hardy. Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond, 1910.
• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison–Wesley. 1997. ISBN 978-0-201-89683-1.. Section 1.2.11: Asymptotic Representations, pp. 107-123.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill. 2001. ISBN 978-0-262-03293-3.. Section 3.1: Asymptotic notation, pp. 41-50.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. стр. 226–228. ISBN 978-0-534-94728-6.  of section 7.1: Measuring complexity.
• Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
• Paul E. Black, "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, "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, "Ω", 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, "ω", 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, "Θ", 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.