Notasi O besar

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Loncat ke navigasi Loncat ke pencarian

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[sunting | sunting sumber]

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

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 x0 sedemikian sehingga

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

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

jika dan hanya jika terdapat bilangan positif δ dan M sedemikian sehingga

Contoh[sunting | sunting sumber]

Dalam penggunaannya, notasi O dapat menyederhanakan fungsi f. Sebagai contoh, misalkan f(x) = 6x4 − 2x3 + 5, fungsi f dapat ditulis sebagai