1 Asimtotik. Deskripsi Materi ini membahas tentang Notasi asymptotic. - презентация

1 1 Asimtotik

2 Deskripsi Materi ini membahas tentang Notasi asymptotic

3 Tujuan Instruksional Khusus (TIK) Menjelaskan Big Oh, Big Omega, Big Teta

4 Notasi Asimtotik Analisa asimtotik biasa digunakan untuk menyelidiki perilaku suatu fungsi atau hubungan antara 2 fungsi berdasarkan beberapa nilai parameter fungsi tersebut yang cenderung menuju suatu nilai asimtot. 4

5 Notasi Big Oh Definisi : bila terdapat 2 buah fungsi f(n) dan g(n) { f(n), g(n) : Z + R + }, maka f(n) adalah Big-Oh dari g(n), atau ditulis: f(n) = O(g(n)), bila konstanta positif c dan n 0 f(n) c. g(n), n n 0. Dalam hal ini dapat dikatakan bahwa f(n) terbatas keatas oleh c.g(n), yang menunjukkan bahwa f tidak bergerak lebih cepat dari pada g. 5

6 Contoh Bila f(n) = n n n, maka dapat dikatakan bahwa f(n) = O(n 3 ). Bukti: n 0, n n n n n n 3 = 121. n 3. Dengan memilih nilai c = 121 dan n 0 = 0, maka definisi tersebut dapat dipenuhi. Untuk fungsi polinomial dengan pangkat sederhana seperti diatas, kita cukup memperhatikan suku dengan pangkat tertinggi, hal ini disebabkan karena suku dengan pangkat tertinggi tersebut memiliki pertumbuhan lebih cepat seiring dengan bertambahnya nilai n; d.p.l. suku dengan pangkat tertinggi akan mendominasi suku-suku yang lain. 6

7 Misal f(n) = 2 log n dan g(n) = (n / 4) 2 Meskipun untuk a g(n), namun g(n) O(f(n)); hal ini disebabkan karena kita tidak dapat menemukan nilai n 0 g(n) c.f(n), n n 0, berapapun besarnya nilai c yang kita pilih. Meskipun demikian kita dapat mengatakan f(n) = O(g(n)), karena kitadapat memilih n 0 = b dan c = 1 f(n) c.g(n), n n0.

8 Sifat Notasi Big-Oh bersifat 1 arah, d.p.l. tidak pernah dinyatakan bahwa bila f(n) = O(g(n)), maka O(g(n)) = f(n). Bila f(n) = O(g(n)) dan h(n) > g(n), n yang cukup besar, maka f(n) = O(h(n)). Contoh: bila f(n) = n 2, dapat dikatakan bahwa f(n) = O(n 3 ). 8

9 Perbandingan pertumbuhan kuadratis dan linier

10 Proposisi Relasi "Big-Oh" bersifat transitif; yakni bila f(n) O(g(n)) dan g(n) O(h(n)), maka f(n) O(h(n)). Untuk sembarang fungsi f dan g { f(n), g(n) : Z + R + }, berlaku: O(f(n)) = O(g(n)) jika dan hanya jika f(n) O(g(n)) dan g(n) O(f(n)). Untuk sembarang fungsi f dan g { f(n), g(n) : Z + R + }, berlaku: O(f(n)) O(g(n)) jika dan hanya jika f(n) O(g(n)) tetapi g(n) O(f(n)). Untuk sembarang fungsi f dan g { f(n), g(n) : Z + R + }, berlaku: O(f(n) + g(n)) = O(max(f(n), g(n)). 10

11 Notasi Omega (Notasi ) Notasi ini menyatakan batas bawah asimtot dari suatu fungsi. Definisi 1.2. : bila terdapat 2 buah fungsi f(n) dan g(n) { f(n), g(n) : Z + R + }, maka f(n) adalah Big-Omega dari g(n), atau ditulis: f(n) = (g(n)), bila konstanta positif c dan n 0 f(n) c. g(n), n n 0. Dalam hal ini dapat dikatakan bahwa f(n) terbatas kebawah oleh c.g(n) yang menunjukkan bahwa f bergerak paling sedikit secepat g. 11

12 Contoh maka bila dipilih n 0 = b dan c = 1, maka dapat dikatakan bahwa g(n) = (f(n)). Meskipun demikian, f(n) (g(n)), karena kita tidak dapat menemukan nilai-nilai c dan n 0 yang dapat memenuhi definisi. Corollary : Untuk sembarang fungsi f(n) dan g(n), yang didefinisikan pada kedua definisi di atas, maka berlaku f(n) = (g(n)), jika dan hanya jika g(n) = O(f(n)). 12

13 Notasi Theta ( Notasi Θ ) Notasi ini menyatakan batas keketatan asimtot dari suatu fungsi. Definisi : bila terdapat 2 buah fungsi f(n) dan g(n) { f(n), g(n) : Z + R + }, maka f(n) adalah Big-Theta dari g(n), atau ditulis: f(n) = Θ(g(n)), bila konstanta positif c 1, c 2 dan n 0 c 1. g(n) f(n) c 2. g(n), n n 0. 13

14 Definisi ini menunjukkan bahwa : f(n) = Θ(g(n)), jika dan hanya jika f(n) = O(g(n)) dan f(n) = (g(n)). atau Θ(f(n)) = O(f(n)) (f(n)).

15 Relasi ekivalen pada Θ Notasi Θ memenuhi relasi ekivalen; yakni untuk sembarang fungsi f dan g { f(n), g(n) : Z+ R+ }, berlaku: 1. f(n) Θ(f(n)) (sifat refleksif) 2. jika f(n) Θ(g(n)), maka g(n) Θ(f(n)) (sifat simetri) 3. jka f(n) Θ(g(n)) dan g(n) Θ(h(n)), maka f(n) Θ(h(n)) (sifat transitif)

16 Untuk sembarang fungsi f dan g { f(n), g(n) : Z + R + }, maka ketiga pernyataan di bawah ini saling ekivalen: O(f(n)) = O(g(n)), (f(n)) = (g(n)), dan f(n) (g(n)).

17 Untuk sembarang fungsi f dan g { f(n), g(n) : Z + R + }, berlaku f(n) (g(n)) jika dan hanya jika f(n) O(g(n)) dan f(n) (g(n)). Jika f(n) O(g(n)), maka O(f(n)) O(g(n)) f(n) O(g(n)) jika dan hanya jika g(n) (f(n)).

18 Catatan Di dalam analisa algoritma, notasi Big-Oh biasa digunakan sebagai batas atas kinerja dari suatu algoritma untuk suatu masalah, sedangkan notasi biasa digunakan untuk menyatakan batas bawah kompleksitas dari persoalan tersebut.

19 Hubungan antar order Bila f(n) berupa suatu polinomial P(n) = a k.n k + a k-1.n k-1 + … + a 1.n + a 0 berderajat k dan a k > 0, maka P(n) ( n k ) (dalam hal ini g(n) = nk). Harus dibuktikan P(n) O(n k ) dan f(n) (n k ).

20 Bukti : P(n) = a k.n k + a k-1.n k-1 + … + a 1.n + a 0 a k.n k + |a k-1 |.n k + … + |a 1 |.n k +|a 0 |. n k (a k + |a k-1 | + … + |a 1 | + |a 0 |). n k Dari sini dipilih c = (a k + |a k-1 | + … + |a 1 | + |a 0 |), sehingga P(n) c. n k, n n 0 = 1, dengan demikian P(n) O( n k ). Selanjutnya….

21 P(n) = a k.n k + a k-1.n k-1 + … + a 1.n + a 0 a k.n k - |a k-1 |.n k - 1 … - |a 1 |.n -|a 0 | = (1/2 a k.n k +1/2 a k.n k ) - |a k-1 |.n k - 1 … - |a 1 |.n -|a 0 | = 1/2 a k.n k +{1/2 a k.n k - |a k-1 |.n k - 1 … - |a 1 |.n -|a 0 |} 1/2 a k.n k +{1/2 a k.n k - |a k-1 |.n k - 1 … - |a 1 |.n k - 1 -|a 0 | n k - 1 } = 1/2 a k.n k +{1/2 a k.n - (|a k-1 | -… - |a 1 | -|a 0 |) } n k - 1 Bila dipilih c = (a k / 2) dan n 0 = ( |a k-1 | - … - |a 1 |- |a 0 |).(2 / a k ), maka P(n) c. n k, n n0. Hal ini berarti P(n) ( n k ).

22 Latihan Diketahui f(n)=4x+5 Buktikan bahwa a. f(n) = O(n) b. f(n) = ( n) c. f(n) = ( n) Diketahui f(n)=2x 2 +6x+3 Buktikan bahwa a. f(n) = O(n 2 ) b. f(n) = ( n 2 ) c. f(n) = ( n 2 )