Notasi O besar

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Notasi O besar (bahasa Inggris: Big O-notation) atau notasi Bachmann–Landau atau notasi asimtotik 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[sunting | sunting sumber]

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

ketika

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

, untuk semua .

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

ketika .

jika dan hanya jika terdapat bilangan positif dan sedemikian sehingga

ketika .

Contoh[sunting | sunting sumber]

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

.