www.wikidata.id-id.nina.az

Notasi O besar atau notasi Bachmann Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan perilaku p

Notasi O besar

Notasi O besar, atau notasi Bachmann–Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan perilaku pada batas suatu fungsi ketika argumen cenderung menuju ke nilai yang khusus atau takhingga. Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh Paul Bachmann, Edmund Landau, dan matematikawan lain. Notasi O yang dipilih Bachmann mengartikan Ordnung, yang berarti orde aproksimasi.

Contoh notasi O besar: karena ada (yakni, ) dan (yakni, ) sehingga dengan .

Notasi O besar dikaitkan dengan notasi yang berbeda. Ada yang menggunakan o, Ω, ω, dan Θ, yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik.

Definisi formal Sunting

Misalkan adalah fungsi bernilai riil ataupun kompleks dan adalah fungsi bernilai riil, dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari bilangan riil positif, sedemikian sehingga bernilai positif untuk semua nilai yang cukup besar, maka

jika dan hanya jika untuk semua nilai yang cukup besar, nilai absolut dari tidak melebihi dikali dengan sebuah konstanta positif. Dengan kata lain, jika dan hanya jika terdapat sebuah bilangan riil positif dan sebuah bilangan riil sedemikian sehingga

Dalam banyak kasus, kita hanya tertarik dengan laju pertumbuhan variabel yang menuju tak hingga sehingga pernyataan tersebut tidak disebutkan lagi, dan hanya ditulis sebagai

Notasi ini juga dapat mendeskripsikan perilaku fungsi di dekat sebuah bilangan riil (biasanya ), maka dapat dikatakan

jika dan hanya jika terdapat bilangan positif dan sedemikian sehingga

Contoh Sunting

Dalam penggunaannya, notasi dapat menyederhanakan fungsi . Sebagai contoh, misalkan , fungsi dapat ditulis sebagai

Referensi Sunting

  1. Bachmann, Paul (1894), Analytische Zahlentheorie [Teori Bilangan Analitik] (dalam bahasa Jerman). Vol. 2. Leipzig: Teubner.
  2. Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Pedoman tentang teori dari distribusi bilangan prima] (dalam bahasa Jerman). Leipzig: B. G. Teubner. hlm. 883.

Bacaan lebih lanjut Sunting

  • Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. 
  • Knuth, Donald (1997). "1.2.11: Asymptotic Representations". Fundamental Algorithms. The Art of Computer Programming. 1 (edisi ke-3rd). Addison-Wesley. ISBN 978-0-201-89683-1. 
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "3.1: Asymptotic notation". Introduction to Algorithms (edisi ke-2nd). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. 
  • Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. hlm. 226–228. ISBN 978-0-534-94728-6. 
  • Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. doi:10.1007/978-3-540-25984-8_27. 
  • Black, Paul E. (11 March 2005). Black, Paul E., ed. "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
  • Black, Paul E. (17 December 2004). Black, Paul E., ed. "little-o notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
  • Black, Paul E. (17 December 2004). Black, Paul E., ed. "Ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
  • Black, Paul E. (17 December 2004). Black, Paul E., ed. "ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
  • Black, Paul E. (17 December 2004). Black, Paul E., ed. "Θ". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 

Pranala luar Sunting

Wikibooks Data Structures memiliki halaman di:
Big-O Notation
Wikiversity solved a MyOpenMath problem using Big-O Notation
wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Notasi O besar atau notasi Bachmann Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan perilaku pada batas suatu fungsi ketika argumen cenderung menuju ke nilai yang khusus atau takhingga Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh Paul Bachmann 1 Edmund Landau 2 dan matematikawan lain Notasi O yang dipilih Bachmann mengartikan Ordnung yang berarti orde aproksimasi Contoh notasi O besar f x O g x displaystyle color red f x in O color blue g x karena ada M gt 0 displaystyle M gt 0 yakni M 1 displaystyle M 1 dan x 0 displaystyle x 0 yakni x 0 5 displaystyle x 0 5 sehingga f x M g x displaystyle color red f x leq color blue Mg x dengan x x 0 displaystyle x geq x 0 Notasi O besar dikaitkan dengan notasi yang berbeda Ada yang menggunakan o W w dan 8 yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik Daftar isi 1 Definisi formal 2 Contoh 3 Referensi 4 Bacaan lebih lanjut 5 Pranala luarDefinisi formal SuntingMisalkan f displaystyle f nbsp adalah fungsi bernilai riil ataupun kompleks dan g displaystyle g nbsp adalah fungsi bernilai riil dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari bilangan riil positif sedemikian sehingga g x displaystyle g x nbsp bernilai positif untuk semua nilai x displaystyle x nbsp yang cukup besar maka f x O g x displaystyle f x O g x nbsp ketika x displaystyle x to infty nbsp jika dan hanya jika untuk semua nilai x displaystyle x nbsp yang cukup besar nilai absolut dari f x displaystyle f x nbsp tidak melebihi g x displaystyle g x nbsp dikali dengan sebuah konstanta positif Dengan kata lain f x O g x displaystyle f x O g x nbsp jika dan hanya jika terdapat sebuah bilangan riil positif M displaystyle M nbsp dan sebuah bilangan riil x 0 displaystyle x 0 nbsp sedemikian sehingga f x M g x displaystyle f x leq Mg x nbsp untuk semua x x 0 displaystyle x geq x 0 nbsp Dalam banyak kasus kita hanya tertarik dengan laju pertumbuhan variabel x displaystyle x nbsp yang menuju tak hingga sehingga pernyataan tersebut tidak disebutkan lagi dan hanya ditulis sebagai f x O g x displaystyle f x O g x nbsp Notasi ini juga dapat mendeskripsikan perilaku fungsi f displaystyle f nbsp di dekat sebuah bilangan riil a displaystyle a nbsp biasanya a 0 displaystyle a 0 nbsp maka dapat dikatakan f x O g x displaystyle f x O g x nbsp ketika x a displaystyle x to a nbsp jika dan hanya jika terdapat bilangan positif d displaystyle delta nbsp dan M displaystyle M nbsp sedemikian sehingga f x M g x displaystyle f x leq Mg x nbsp ketika 0 lt x a lt d displaystyle 0 lt x a lt delta nbsp Contoh SuntingDalam penggunaannya notasi O displaystyle O nbsp dapat menyederhanakan fungsi f displaystyle f nbsp Sebagai contoh misalkan f x 6 x 4 2 x 3 5 displaystyle f x 6x 4 2x 3 5 nbsp fungsi f displaystyle f nbsp dapat ditulis sebagai f x O x 4 displaystyle f x O x 4 nbsp Referensi Sunting Bachmann Paul 1894 Analytische Zahlentheorie Teori Bilangan Analitik dalam bahasa Jerman Vol 2 Leipzig Teubner Landau Edmund 1909 Handbuch der Lehre von der Verteilung der Primzahlen Pedoman tentang teori dari distribusi bilangan prima dalam bahasa Jerman Leipzig B G Teubner hlm 883 Bacaan lebih lanjut SuntingHardy G H 1910 Orders of Infinity The Infinitarcalcul of Paul du Bois Reymond Cambridge University Press Knuth Donald 1997 1 2 11 Asymptotic Representations Fundamental Algorithms The Art of Computer Programming 1 edisi ke 3rd Addison Wesley ISBN 978 0 201 89683 1 Cormen Thomas H Leiserson Charles E Rivest Ronald L Stein Clifford 2001 3 1 Asymptotic notation Introduction to Algorithms edisi ke 2nd MIT Press and McGraw Hill ISBN 978 0 262 03293 3 Sipser Michael 1997 Introduction to the Theory of Computation nbsp PWS Publishing hlm 226 228 ISBN 978 0 534 94728 6 Avigad Jeremy Donnelly Kevin 2004 Formalizing O notation in Isabelle HOL PDF International Joint Conference on Automated Reasoning doi 10 1007 978 3 540 25984 8 27 Black Paul E 11 March 2005 Black Paul E ed big O notation Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology Diakses tanggal December 16 2006 Black Paul E 17 December 2004 Black Paul E ed little o notation Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology Diakses tanggal December 16 2006 Black Paul E 17 December 2004 Black Paul E ed W Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology Diakses tanggal December 16 2006 Black Paul E 17 December 2004 Black Paul E ed w Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology Diakses tanggal December 16 2006 Black Paul E 17 December 2004 Black Paul E ed 8 Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology Diakses tanggal December 16 2006 Pranala luar Sunting nbsp Wikibooks Data Structures memiliki halaman di Big O Notation nbsp Wikiversity solved a MyOpenMath problem using Big O Notation Growth of sequences OEIS Online Encyclopedia of Integer Sequences Wiki Landau Symbols Big O Notation What is it good for Big O Notation explained in plain english An example of Big O in accuracy of central divided difference scheme for first derivative Diarsipkan 2018 10 07 di Wayback Machine A Gentle Introduction to Algorithm Complexity Analysis Diperoleh dari https id wikipedia org w index php title Notasi O besar amp oldid 22756554