Notasi O besar

Contoh notasi O besar: f ( x ) ∈ O ( g ( x ) ) {\displaystyle {\color {red}f(x)}\in O{\color {blue}(g(x))}} ${\color {red}f(x)}\in O{\color {blue}(g(x))}$ karena ada M > 0 {\displaystyle M>0} $M>0$ (yakni, M = 1 {\displaystyle M=1} $M=1$ ) dan x 0 {\displaystyle x_{0}} $x_{0}$ (yakni, x 0 = 5 {\displaystyle x_{0}=5} $x_{0}=5$ ) sehingga f ( x ) ≤ M g ( x ) {\displaystyle {\color {red}f(x)}\leq {\color {blue}Mg(x)}} ${\color {red}f(x)}\leq {\color {blue}Mg(x)}$ dengan x ≥ x 0 {\displaystyle x\geq x_{0}} $x\geq x_{0}$ .

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.

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

Misalkan f {\displaystyle f} $f$ adalah fungsi bernilai riil ataupun kompleks dan g {\displaystyle g} $g$ adalah fungsi bernilai riil, dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari bilangan riil positif, sedemikian sehingga g ( x ) {\displaystyle g(x)} $g(x)$ bernilai positif untuk semua nilai x {\displaystyle x} $x$ yang cukup besar, maka

f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} $f(x)=O(g(x))$ ketika x → ∞ {\displaystyle x\to \infty } $x\to \infty$

jika dan hanya jika untuk semua nilai x {\displaystyle x} $x$ yang cukup besar, nilai absolut dari f ( x ) {\displaystyle f(x)} $f(x)$ tidak melebihi g ( x ) {\displaystyle g(x)} $g(x)$ dikali dengan sebuah konstanta positif. Dengan kata lain, f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} $f(x)=O(g(x))$ jika dan hanya jika terdapat sebuah bilangan riil positif M {\displaystyle M} $M$ dan sebuah bilangan riil x 0 {\displaystyle x_{0}} $x_{0}$ sedemikian sehingga

| f ( x ) | ≤ M g ( x ) {\displaystyle |f(x)|\leq \;Mg(x)} $|f(x)|\leq \;Mg(x)$ , untuk semua x ≥ x 0 {\displaystyle x\geq x_{0}} $x\geq x_{0}$ .

Dalam banyak kasus, kita hanya tertarik dengan laju pertumbuhan variabel x {\displaystyle x} $x$ 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))} $f(x)=O(g(x))$ .

Notasi ini juga dapat mendeskripsikan perilaku fungsi f {\displaystyle f} $f$ di dekat sebuah bilangan riil a {\displaystyle a} $a$ (biasanya a = 0 {\displaystyle a=0} $a=0$ ), maka dapat dikatakan

f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} $f(x)=O(g(x))$ ketika x → a {\displaystyle x\to a} $x\to a$ .

jika dan hanya jika terdapat bilangan positif δ {\displaystyle \delta } $\delta$ dan M {\displaystyle M} $M$ sedemikian sehingga

| f ( x ) | ≤ M g ( x ) {\displaystyle |f(x)|\leq \;Mg(x)} $|f(x)|\leq \;Mg(x)$ ketika 0 < | x − a | < δ {\displaystyle 0<|x-a|<\delta } $0<|x-a|<\delta$ .

Contoh

Dalam penggunaannya, notasi O {\displaystyle O} $O$ dapat menyederhanakan fungsi f {\displaystyle f} $f$ . Sebagai contoh, misalkan f ( x ) = 6 x 4 − 2 x 3 + 5 {\displaystyle f(x)=6x^{4}-2x^{3}+5} $f(x)=6x^{4}-2x^{3}+5$ , fungsi f {\displaystyle f} $f$ dapat ditulis sebagai

f ( x ) = O ( x 4 ) {\displaystyle f(x)=O(x^{4})} $f(x)=O(x^{4})$ .

Referensi

↑ 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

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. Vol. 1 (Edisi 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 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 Maret 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal Desember 16, 2006.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
Black, Paul E. (17 Desember 2004). Black, Paul E. (ed.). "little-o notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal Desember 16, 2006.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
Black, Paul E. (17 Desember 2004). Black, Paul E. (ed.). "Ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal Desember 16, 2006.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
Black, Paul E. (17 Desember 2004). Black, Paul E. (ed.). "ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal Desember 16, 2006.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
Black, Paul E. (17 Desember 2004). Black, Paul E. (ed.). "Θ". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal Desember 16, 2006.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)