SURIANI D121181316_Notasi Big O

"Notasi Big O" (pengukuran kompleksitas algoritma)

DEFINISI

Notasi diperkenalkan pertama kali di Jerman, oleh seorang  number theorist Paul Bachmann pada tahun  1894, pada edisi kedua dari bukunya yang berjudul  Analytische Zahlentheorie (“analitik teori bilangan”),  dari edisi pertama yang (belum membahas notasi O besar) yang diterbitkan pada 1892. Notasi ini menjadi  populer oleh  number theorist  Jerman yang lain, Edmund Landau, sehingga terkadang notasi ini disebut  Notasi Landau. O Besar adalah singkatan dari “order of”  dalam bahasa Inggris, yang sebenarnya adalah  lambang Omicron besar, belakangan digunakan huruf latin dengan bentuk yang identik yaitu huruf “O”  besar, bukan 0(bilangan nol)

 

Notasi O besar atau yang lazim disebut dengan Big-O Notation adalah sebuah cara atau metode untuk melakukan analisa terhadap sebuah algoritma pemrograman terhadap waktu eksekusi. Tentang seberapa efisien dan kompleksitas barisan kode dalam dimensi waktu.

Menurut Wikipedia,  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.

Notasi Big O mengukur kompleksitas algoritma dalam dimensi waktu. Selain Big O, ada dua notasi lain yang dapat digunakan untuk mengukur kompleksitas waktu sebuah algoritma, yaitu Big Theta dan Big Omega. Konsep Big Omega mirip dengan Big O. Perbedaan kedua konsep tersebut terletak pada semantiknya. Nilai Big Omega menunjukkan batas bawah kompleksitas waktu suatu algoritma, sedangkan Big O sebaliknya. Apabila sebuah algoritma memiliki nilai batas atas dan batas bawah yang sama, algoritma tersebut dikatakan memenuhi konsep Big Theta.

 

KEGUNAAN

Biasanya, notasi O besar digunakan untuk menggambarkan batas - batas asimptotik. Namun batas asimptotik  tersebut lebih umum dan tepat dinotasikan simbol dengan T (theta besar) seperti akan dijelaskan dibawah ini.

 

Terdapat dua macam penggunaan notasi ini:

Asimptotik Tak Hingga (Infinite Asymptotik) dan Asimptotik Sangat Kecil (Inifinitesimal Asymptotik). Perbedaan keduanya hanya terdapat pada aplikasi, bukan pada konsep dasarnya. Definsi umum dari “O Besar” adalah sama untuk kedua kasus, namun dengan batas-batas (limits) yang berbeda untuk argumen fungsi-nya.

Infinite Asymptotic

Notasi O Besar sangat berguna untuk mengnalisa  efisiensi suatu algoritma. Misalnya,  waktu yang  diperlukan untuk menyelesaikan sebuah masalah  dengan parameter n bisa jadi

 

T(n) = 4n2–2n + 2

 

Semakin n bertambah besar, suku n2 akan mendominasi pertumbuhan, sehingga suku-suku  yang lain dapat diabaikan – sebagai perumpama-an, jika n = 500, suku 4n2 akan 1000 kali lebih  besar daripada suku 2n, sehingga mengabaikan  suku-suku yang lebih kecil tidak akan memberikan efek yang cukup signifikan.

Lebih jauh lagi, koefisien dari suku tersebut menjadi tidak relevan / dapat diabaikan. Misalnya ekspresi yang mengandung suku n2 atau 2n. Meskipun T(n) = 1.000.000n2,  jika U(n)  = nx, koefisien selalu dapat diabaikan, karena n berkembang lebih besar dari 1.000.000. (T(1.000.000)) = 1.000.000 x = U(1.000.000)).

 

Infinitesimal Asymptotic

Notasi O Besar dapat pula digunakan untuk menggambarkan kesalahan dalam sebuah aproksimasi dalam fungsi matematika. Seperti misalnya : Mengekspresikan bahwa kesalahannya, memiliki selisih dan lebih kecil dalam nilai absolut dibandingkan waktu konstan |n|3 untuk x mendekati 0. Dalam analisa asimptotik, kita lebih mementingkan kecenderungan ukuran (order of magnitude) daripada nilai aktual/sebenarnya dari sebuah fungsi. Dan lagi, kita tidak perlu mengetahui berapa lama waktu yang dibutuhkan untuk melakukan suatu operasi pada jenis komputer tertentu. Yang jelas, kita dengan mudah dapat melihat bahwa “n2“ adalah fungsi yang berkembang jauh lebih cepat dibandingkan fungsi linear seperi “n”. Untuk menggambarkan kecenderungan ukuran dari suatu operasi, kita menggunakan “Notasi O Besar”. Jika kita memiliki algoritma yang melakukan 7n4 + 35n3 – 19n2 + 3 operasi, Notasi O Besarnya adalah O(n4). Jika kita memiliki algoritma yang melakukan 2n + 5 operasi, Notasi O Besarnya adalah O(n). Perhitungan tersebut cukup sederhana.

 

 

CONTOH

Ambil sebuah polinom Dikatakan f(x) memiliki kecenderungan O(g(x)) atau O(x4). Dari definisi kecenderungan,

|f(x)| < C |g(x)| dimana C konstan.

Pembuktian:

Untuk x > 1 Karena x4 > x3 dan seterusnya.. dengan C = 13.