Pertemuan 5 - Notasi Asimtotik [PDF]

Citation preview

Analisis Algoritma Pertemuan 5 Notasi Asimptotik Dosen : Chrismikha Hardyanto S.Kom., M.Kom.



1



AGENDA PERKULIAHAN  Pengantar Notasi Asimtotik  Notasi Big Oh (O)  Notasi Big Omega (Ω)



 Notasi Big Theta ()



2



Pada pertemuan ke-4, Anda sudah mempelajari bagaimana cara mengukur kebutuhan waktu algoritma Menggunakan konsep kompleksitas waktu T(n)



Pada analisis efisiensi waktu algoritma, ada konsep lain yang dapat digunakan yaitu notasi asimptotik



Latar Belakang Dalam praktisnya , Timbul permasalahan pada konsep T(n)



1. Ukuran kompleksitas waktu T(n) yang dituliskan secara detail/spesifik bukanlah menjadi hal yang sangat penting untuk bisa memberikan gambaran ukuran kebutuhan



waktu suatu algoritma.



2. Ukuran dari Variabel n (nilai input dari



algoritma) yang akan menjadi penentu



laju pertumbuhan dari kebutuhan waktu suatu algoritma ketika di eksekusi



komputer.



5



Pengaruh n terhadap pertumbuhan waktu



Tingkat Pertumbuhan: n



2n2 + 6n + 1



n2



1



9



1



10



261



100



100



2.061



1.000



1.000



2.006.001



1.000.000



dua persamaan tersebut memiliki tingkat



10.000



2.000.060.001



1.000.000.000



pertumbuhan waktu yang sebanding



Apabila diperhatikan,



6



2 n



Oleh karena itu, persamaan dapat digunakan untuk bisa mewakili orde dari T(n) . Itulah gambaran notasi asimptotik



(sumber : rinaldi munir)



Notasi Asimptotik  Notasi asimptotik di definisikan sebagai suatu notasi yang menggambarkan kelas - kelas pertumbuhan waktu akibat pengaruh masukan data (n) dari algoritma ketika dieksekusi.  Ada 3 jenis notasi asimptotik, yaitu :







Notasi Big Oh (O)







Notasi Big Omega (Ω)







Notasi Big Theta ()



8



Notasi 1 : Notasi Big Oh (O)



Notasi Big Oh (O) T(n) merupakan himpunan bagian dari O(g(n)), Jika fungsi T(n) memiliki tingkat pertumbuhan lebih kecil atau sama dengan g(n), dimana T(n) dibatasi atas beberapa pengali konstan(c) dari g(n) untuk semua ukuran n.



10



Ilustrasi T(n) ϵ O(g(n))



Pertumbuhan waktu T(n) tidak akan



pernah melewati garis/batas atas dari cg(n)



11



Contoh



Buktikan: 10n + 5 ϵ O(n2)



Penyelesaian: Cari c dan n0, sehingga T(n) < cg(n) untuk semua n > n0



10n + 5 < O(n2) 10n + 5 < 10n2 + 5n



2



10n + 5 < 15n2 untuk c = 15, n0 = 1



12



Contoh



Buktikan: 2n2 + 6n + 1 ϵ O(n2)



Penyelesaian: Cari c dan n0, sehingga T(n) < cg(n) untuk semua n > n0



2n2 +6n + 1 < O(n2) 2n2 +6n + 1 < 2n2 +6n2 + 1n2



2n2 +6n + 1 < 9n2 untuk c = 9, n0 = 1



13



KESIMPULAN : Notasi Big Oh (O) digunakan untuk menggabarkan batas atas dari laju pertumbuhan waktu algoritma. (kemungkinan waktu terburuk)



(sumber : rinaldi munir)



Notasi 2 : Notasi Big Omega (Ω)



Notasi Big Omega (Ω) T(n) merupakan himpunan bagian dari Ω(g(n)) Jika fungsi T(n) memiliki tingkat pertumbuhan lebih besar atau sama dengan g(n), dimana T(n) dibatasi bawah terhadap beberapa pengali konstan (c) dari g(n) untuk semua ukuran n.



16



Ilustrasi T(n) ϵ Ω(g(n))



Pertumbuhan



waktu



T(n)



selalu



berada diatas garis/batas bawah dari cg(n)



17



Contoh



Buktikan: n3 ϵ Ω(n2)



Penyelesaian: Cari c dan n0, sehingga T(n) > cg(n) untuk semua n > n0



n3 > Ω(n2) n3 > n2



untuk c = 1, n0 = 1



12



KESIMPULAN : Notasi Big Omega (Ω) digunakan untuk menggabarkan batas bawah dari laju pertumbuhan waktu algoritma (kemungkinan waktu terbaik)



(sumber : rinaldi munir)



Notasi 3 : Notasi Big Theta ()



Notasi Big Theta () T(n) merupakan himpunan bagian dari



(g(n)) Jika fungsi T(n) memiliki tingkat pertumbuhan yang sama dengan g(n),



dimana



T(n)



dibatasi



atas



dan



bawah



terhadap beberapa pengali konstan (c) dari



g(n) untuk semua ukuran n.



16



Ilustrasi T(n) ϵ (g(n))



Pertumbuhan



waktu



T(n)



Selalu



berada dibawah garis/batas atas dari



c1g(n)



diatas



dan



selalu



garis/batas



berada



bawah



dari



c2g(n)



17



Contoh



Buktikan: 𝟏 𝒏(n+1) 𝟐



ϵ (n2)



Penyelesaian: Cari c dan n0, sehingga c2g(n) < T(n) < c1g(n) untuk semua n > n0



Batas atas : 𝟏 2 𝒏 𝟐



𝟏



+ 𝟐 𝒏 < n2 , Untuk semua n > 1 (dimana c = 1, n0 = 1)



Batas bawah : 𝟏 2 𝒏 𝟐



+



𝟏 𝒏 𝟐



>



𝟏 2 𝒏 𝟐



𝟏 , Untuk semua n > 1 (dimana c = , n0 = 1) 𝟐



KESIMPULAN : Notasi Big Theta () digunakan untuk menggabarkan laju pertumbuhan waktu algoritma yang berada diantara batas atas dan batas bawah. (kemungkinan waktu rata-rata) (sumber : rinaldi munir)



Dari ketiga Notasi tersebut Mana Notasi yang paling banyak digunakan untuk mengukur kebutuhan waktu algoritma ??



“Big Oh (O)”



Terima Kasih



30