Notasi O besar: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Bot: Penggantian teks otomatis (-algoritma; +algoritme) |
Menambah definisi dan contoh sederhana |
||
Baris 1:
'''Notasi O besar''' (big-O notation) atau '''notasi Landau''' adalah [[notasi matematika]] yang digunakan terutama pada bidang ilmu komputer (computer science). Notasi ini digunakan untuk menyatakan keefektifan sebuah algoritme. Notasi ini bekerja dengan cara memperhitungkan input yang diberikan oleh user.
== Definisi Formal ==
Misalkan ''f'' adalah fungsi bernilai riil ataupun kompleks dan ''g'' adalah fungsi bernilai riil, dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari [[bilangan riil]] positif, sedemikian sehingga ''g(x)'' bernilai positif untuk semua nilai ''x'' yang cukup besar, maka
:<math>f(x)=O(g(x))\text{ as }x\to\infty</math>
[[jika dan hanya jika]] untuk semua nilai ''x'' yang cukup besar, nilai absolut dari ''f''(''x'') tidak melebihi ''g''(''x'') dikali dengan sebuah konstanta positif. Dengan kata lain, ''f''(''x'') = ''O''(''g''(''x'')) jika dan hanya jika terdapat sebuah bilangan riil positif ''M'' dan sebuah bilangan riil ''x''<sub>0</sub> sedemikian sehingga
:<math>|f(x)| \le \; M g(x)\text{ for all }x \ge x_0.</math>
Dalam banyak kasus, kita hanya tertarik dengan laju pertumbuhan variabel ''x'' 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 ''f'' di dekat sebuah bilangan riil ''a'' (biasanya ''a'' = 0), maka dapat dikatakan
:<math>f(x)=O(g(x))\text{ as }x\to a</math>
jika dan hanya jika terdapat bilangan positif ''δ'' dan ''M'' sedemikian sehingga
:<math>|f(x)| \le \; M g(x)\text{ when } 0 < |x - a| < \delta.</math>
== Contoh ==
Dalam penggunaannya, notasi ''O'' dapat menyederhanakan fungsi ''f''. Sebagai contoh, misalkan ''f''(''x'') = 6''x''<sup>4</sup> − 2''x''<sup>3</sup> + 5, fungsi ''f'' dapat ditulis sebagai
:<math>f(x) = O(x^4)</math>
{{matematika-stub}}
| |||