Notasi Big O

Posted on February 28, 2010 by Nursatria

Saya mau menjelaskan notasi Big-O, suatu notasi yang dikembangkan oleh matematika tetapi banyak dipakai dalam ilmu-ilmu lain, seperti ilmu kompeter (tepatnya algoritma kompleksitas), statistik, fisika dan ilmu-ilmu teknik. Big-O adalah hubungan kedua fungsi ketika nilai kedua fungsi tersebut menuju tak hingga

Definisi: Diberikan 2 buah fungsi f dan g yang keduanya merupakan fungsi pada bilangan real. f\left(n\right)=O\left(g\left(n\right)\right) disebut f\left(n\right) Big-O dari g\left(n\right) jika terdapat dua buah bilangan real postif C dan n_0, untuk semua n\geq n_{0} berlaku f\left(n\right)\leq Cg\left(n\right). Dalam bentuk notasi ditulis

f\left(n\right)=O\left(g\left(n\right)\right)\leftrightarrow\left\{ \exists C>0,\,\exists n_{0}>0,\,\forall n\geq n_{0}:f\left(n\right)\leq g\left(n\right)\right\}

Beberapa literatur menotasikan f\left(n\right)=O\left(g\left(n\right)\right) dengan f\left(n\right)\in O\left(g\left(n\right)\right). Jadi jangan bingung jika melihat notasi f\left(n\right)\in O\left(g\left(n\right)\right) itu sama dengan f\left(n\right)=O\left(g\left(n\right)\right)

Secara Geometri f\left(n\right)=O\left(g\left(n\right)\right) dapat digambarkan sebagai berikut

Contoh: 40n+100=O\left(n^{2}+10n+300\right), dengan mudah kita ketahui 0\leq40n+100\leq n^{2}+10n+300 untuk semua n\geq20. Jika kita ambil n_0=20 dan C=1 maka terbukti 40n+100=O\left(n^{2}+10n+300\right)

Catetan dari contoh diatas, sebarang nilai n_0 yang lebih besar dari 20 juga memenuhi definisi big-O begitupula sebarang nilai C yang lebih besar dari 1 juga memenuhi. Secara umum jika 2 buah fungsi memenuhi definisi f\left(n\right)=O\left(g\left(n\right)\right), itu artinya terdapat pasangan bilangan real positif n_0 dan C yang tak hingga banyaknya yang memenuhi f\left(n\right)\leq Cg\left(n\right) untuk semua n\geq n_{0}. Untuk membuktikan f\left(n\right)=O\left(g\left(n\right)\right) kita tidak harus mencari nilai terkecil dari n_0 atau mencari nilai terkecil dari C, cukup ditunjukan satu cantoh pasangan n_0 dan C yang memenuhi definsi Big-0.

Notasi-notasi yang berhubungan dengan Big-O.

Saya akan menjelaskan secara singkat 2 buah notasi yang berhubungan dengan Bing-O, akan saya lengkapi gambar untuk memudahkan pemahaman

Definisi: Diberikan 2 buah fungsi f dan g yang keduanya merupakan fungsi pada bilangan real. f\left(n\right)=\Omega\left(g\left(n\right)\right) dikatakan f(n) Big Omega dari g(n), jika terdapat dua buah bilangan real postif C dan n_0, untuk semua n\geq n_{0} berlaku Cg\left(n\right)\leq f\left(n\right).

Gambar geometriknya

Dengan mudah kita peroleh hunungan Big-O dengan Big-Omega sebagai berikut

Teorema: f\left(n\right)=O\left(g\left(n\right)\right) jika hanya jika . g\left(n\right)=\Omega\left(f\left(n\right)\right).

Notasi selanjutnya

Definisi: Diberikan 2 buah fungsi f dan g yang keduanya merupakan fungsi pada bilangan real. f\left(n\right)=\Theta\left(g\left(n\right)\right) dikatakan f(n) Big Theta dari g(n), jika terdapat tiga buah bilangan real postif n_0,  C_0 dan C_1, untuk semua n\geq n_{0} berlaku C_{0}g\left(n\right)\leq f\left(n\right)\leq C_{1}g\left(n\right)

Gambar geometriknya.

Nah..sekarang bagaimana menunjukkan 2 buah fungsi memeuhi Big-O, Big-Omega atau Big-Theta? Itu kapan-kapan saya jelasin yach :mrgreen

———————————————————————————————————————————————-
**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

Advertisement

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in Analisis and tagged , , , , . Bookmark the permalink.

8 Responses to Notasi Big O

  1. putri says:
    June 25, 2015 at 13:26

    kalau boleh tau itu referensinya dari mana ya?buku atau jurnal apa?

    Reply
  2. putri says:
    June 25, 2015 at 11:39

    boleh tau definisi big O dari literatur mana ya.?

    Reply
  3. deki_satria says:
    November 7, 2011 at 14:11

    lah, ado kak master handrie noprison
    klao maksud O(1) apa ya gan ?

    Reply
  5. 23Pstars says:
    October 21, 2010 at 06:27

    terimakasih gan,,,, kebetulan sy nyari2 referensi untuk materi ini,,, 😀

    Reply
  6. mijla says:
    September 23, 2010 at 15:23

    trims atas penjelasan…pa

    klo perbedaan dengan little O dan Teta O
    apa ya ?

    Reply
  7. Erwin says:
    March 25, 2010 at 10:29

    Gila… hebat uy..

    Reply

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s