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 „“, „“, „“ 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
[uredi | uredi izvor]"≤"
[uredi | uredi izvor]![](http://upload.wikimedia.org/wikipedia/sr/thumb/7/7c/Landau_simboli_o_slikovit_primer.png/244px-Landau_simboli_o_slikovit_primer.png)
znači da asimptotski ne raste brže od , a definisano je tako što je izraz ograničen nekom konstantom .
Ista definicija, nešto drugačije napisana glasi:
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
"≥"
[uredi | uredi izvor]Oznaka 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 je sporija ili u najboljem slučaju isto brza kao g).
Isto to nešto jednostavnijom formulom glasi:
"="
[uredi | uredi izvor]znači da f i g asimptotski gledano jednako brzo rastu, a to definišemo koristeći se ponovo prethodnim definicijama: i , odnosno .
Uz pomoć limesa:
"<"
[uredi | uredi izvor]znači da g asimptotski sporije raste od f. Definisano je tako da je nulti red.
">"
[uredi | uredi izvor]Oznaka znači da je g asimptotski brža od f. Kao i kod i tako se i ovde služimo suprotnom definicijom: .
Pravila za računanje sa O notacijom
[uredi | uredi izvor]- za neko
- za neko
- za neko
- za neku konstantu
- , za ; tj. baza logaritma nije bitna, samo nek je veća od 1
Literatura
[uredi | uredi izvor]- 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.