Notasi O besar: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
Fitur saranan suntingan: 2 pranala ditambahkan. Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
||
| (39 revisi perantara oleh 19 pengguna tidak ditampilkan) | |||
Baris 1:
[[File:Big-O-notation.png|300px|thumb|Contoh notasi O besar: <math>{\color{red}f(x)} \in O{\color{blue}(g(x))}</math> karena ada <math>M>0</math> (yakni, <math>M=1</math>) dan <math>x_0</math> (yakni, <math>x_0=5</math>) sehingga <math>{\color{red}f(x)}\leq {\color{blue}Mg(x)}</math> dengan <math>x\geq x_0</math>.]]'''Notasi ''O'' besar''', atau '''notasi''' '''Bachmann–Landau''' atau '''notasi asimtotik''' merupakan [[notasi matematika]] yang menjelaskan [[Analisis asimtotik|perilaku pada batas]] suatu [[Fungsi (matematika)|fungsi]] ketika [[Argumen fungsi|argumen]] cenderung menuju ke nilai yang khusus atau takhingga. Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh [[Paul Gustav Heinrich Bachmann|Paul Bachmann]],<ref>[[Paul Bachmann|Bachmann, Paul]] (1894), [https://archive.org/stream/dieanalytischeza00bachuoft#page/402/mode/2up ''Analytische Zahlentheorie''] [''Teori Bilangan Analitik''] (dalam bahasa Jerman). Vol. 2. Leipzig: Teubner.</ref> [[Edmund Landau]],<ref>[[Edmund Landau|Landau, Edmund]] (1909). ''[[iarchive:handbuchderlehre01landuoft|Handbuch der Lehre von der Verteilung der Primzahlen]]'' [''Pedoman tentang teori dari distribusi bilangan prima''] (dalam bahasa Jerman). Leipzig: B. G. Teubner. hlm. 883.</ref> dan matematikawan lain. Notasi O yang dipilih Bachmann mengartikan ''[[:wikt:Ordnung#German|Ordnung]]'', yang berarti [[orde aproksimasi]].
Notasi O besar dikaitkan dengan notasi yang berbeda. Ada yang menggunakan {{math|''o'', Ω, ''ω''}}, dan {{math|Θ}}, yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik.
== Definisi formal ==
Misalkan <math>f</math> adalah fungsi bernilai riil ataupun kompleks dan <math>g</math> adalah fungsi bernilai riil, dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari [[bilangan riil]] positif, sedemikian sehingga <math>g(x)</math> bernilai positif untuk semua nilai <math>x</math> yang cukup besar, maka
: <math>f(x)=O(g(x))</math> ketika <math>x\to\infty</math>
[[jika dan hanya jika]] untuk semua nilai <math>x</math> yang cukup besar, [[nilai absolut]] dari <math>f(x)</math> tidak melebihi <math>g(x)</math> dikali dengan sebuah konstanta positif. Dengan kata lain, <math>f(x)=O(g(x))</math> jika dan hanya jika terdapat sebuah bilangan riil positif <math>M</math> dan sebuah bilangan riil <math>x_0</math> sedemikian sehingga
: <math>|f(x)| \le \; M g(x)</math>, untuk semua <math>x \ge x_0</math>.
Dalam banyak kasus, kita hanya tertarik dengan laju pertumbuhan variabel <math>x</math> yang menuju tak hingga sehingga pernyataan tersebut tidak disebutkan lagi, dan hanya ditulis sebagai
: <math>f(x) = O(g(x))</math>.
Notasi ini juga dapat mendeskripsikan perilaku fungsi <math>f</math> di dekat sebuah bilangan riil <math>a</math> (biasanya <math>a=0</math>), maka dapat dikatakan
: <math>f(x)=O(g(x))</math> ketika <math>x\to a</math>.
jika dan hanya jika terdapat bilangan positif <math>\delta</math> dan <math>M</math> sedemikian sehingga
: <math>|f(x)| \le \; M g(x)</math> ketika <math>0 < |x - a| < \delta</math>.
== Contoh ==
Dalam penggunaannya, notasi <math>O</math> dapat menyederhanakan fungsi <math>f</math>. Sebagai contoh, misalkan <math>f(x) = 6x^4 - 2x^3 + 5</math>, fungsi <math>f</math> dapat ditulis sebagai
: <math>f(x) = O(x^4)</math>.
== Referensi ==
<references />
== Bacaan lebih lanjut ==
* {{cite book | first=G. H. | last=Hardy | author-link=G. H. Hardy | title=Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond | date=1910 | url=https://archive.org/details/ordersofinfinity00harduoft | publisher=[[Cambridge University Press]]}}
* {{cite book | first=Donald | last=Knuth | author-link=Donald Knuth | title=Fundamental Algorithms | volume=1 | series=The Art of Computer Programming | edition=3rd | publisher=Addison-Wesley | date=1997 | isbn=978-0-201-89683-1 | section=1.2.11: Asymptotic Representations}}
* {{cite book | first1=Thomas H. | last1=Cormen | author-link1=Thomas H. Cormen | first2=Charles E. | last2=Leiserson | author-link2=Charles E. Leiserson | first3=Ronald L. | last3=Rivest | author-link3=Ronald L. Rivest | first4=Clifford | last4=Stein | author-link4=Clifford Stein | title=Introduction to Algorithms | edition=2nd | publisher=MIT Press and McGraw-Hill | date=2001 | isbn=978-0-262-03293-3 | section=3.1: Asymptotic notation| title-link=Introduction to Algorithms }}
* {{cite book | first=Michael | last=Sipser | author-link=Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | url=https://archive.org/details/introductiontoth00sips_928 | url-access=limited | publisher = PWS Publishing | isbn = 978-0-534-94728-6 | pages=[https://archive.org/details/introductiontoth00sips_928/page/n239 226]–228}}
* {{cite conference | first1=Jeremy | last1=Avigad | first2=Kevin | last2=Donnelly | url=http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf | title=Formalizing O notation in Isabelle/HOL | doi=10.1007/978-3-540-25984-8_27 | conference=International Joint Conference on Automated Reasoning | date=2004}}
* {{cite web | first=Paul E. | last=Black | url=https://xlinux.nist.gov/dads/HTML/bigOnotation.html | title=big-O notation | work=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | date=11 March 2005 | access-date=December 16, 2006}}
* {{cite web | first=Paul E. | last=Black | url=https://xlinux.nist.gov/dads/HTML/littleOnotation.html | title=little-o notation | work=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | date=17 December 2004 | access-date=December 16, 2006}}
* {{cite web | first=Paul E. | last=Black | url=https://xlinux.nist.gov/dads/HTML/omegaCapital.html | title=Ω | work=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | date=17 December 2004 | access-date=December 16, 2006}}
* {{cite web | first=Paul E. | last=Black | url=https://xlinux.nist.gov/dads/HTML/omega.html | title=ω | work=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | date=17 December 2004 | access-date=December 16, 2006}}
* {{cite web | first=Paul E. | last=Black | url=https://xlinux.nist.gov/dads/HTML/theta.html | title=Θ | work=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | date=17 December 2004 | access-date=December 16, 2006}}
== Pranala luar ==
{{Wikibooks|Data Structures|Asymptotic Notation#Big-O Notation|Big-O Notation}}
{{sister project|project=wikiversity|text=Wikiversity solved a [[v:MyOpenMath/Solutions|''MyOpenMath problem'']] using '''''[[v:MyOpenMath/Solutions/Big-O|Big-O Notation]]'''''}}
* [http://oeis.org/wiki/Growth_of_sequences Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki]
* [http://mathworld.wolfram.com/LandauSymbols.html Landau Symbols]
* [http://www.perlmonks.org/?node_id=573138 Big-O Notation – What is it good for]
* [https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/50288253#50288253 Big O Notation explained in plain english]
*[https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ An example of Big O in accuracy of central divided difference scheme for first derivative] {{Webarchive|url=https://web.archive.org/web/20181007223123/https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ |date=2018-10-07 }}
*[https://discrete.gr/complexity/ A Gentle Introduction to Algorithm Complexity Analysis]
[[Kategori:Mathematical notation]]
[[Kategori:Asymptotic analysis]]
[[Kategori:Analysis of algorithms]]
[[Kategori:Notasi matematika]]
[[Kategori:Analisis asimtotik]]
[[Kategori:Analisis algoritma]]
| |||