wijanarto - dinus.ac.iddinus.ac.id/repository/docs/ajar/slide_3.pdf · contoh "contoh berikut...

Notasi Asimptotik

wijanarto

Definisi

• Notasi asimtotik menyatakan batas fungsi-fungsi tersebut apabila nilai n semakin besar,jadi Notasi asimtotik merupakan himpunanfungsi yang dibatasi oleh suatu fungsi n Nyang cukup besar.

• Contoh– 1000 n2 ≤ n3 ; untuk n ≥ 1000

• Notasi asimtotik menyatakan batas fungsi-fungsi tersebut apabila nilai n semakin besar,jadi Notasi asimtotik merupakan himpunanfungsi yang dibatasi oleh suatu fungsi n Nyang cukup besar.

• Contoh– 1000 n2 ≤ n3 ; untuk n ≥ 1000

Kompleksitas Asimptotik

• Cara mengungkapkan komponen utama costdari algoritma, dengan menggunakan unitideal kerja komputasi.

Contoh

• Contoh berikut adalah, jika pada RAM menghasilkanwaktu tempuh (1) 10n3+5n2+7, kita tahu bahwa T(n)tersebut berada pada area kubik, dan jika komputerlain menghasilkan (2) 2n3+3n+79, hal ini seharusnyadapat di nyatakan juga berada dalam ranah kubik.

• Dengan demikian ( 1) dan ( 2) berada pada kelasyang sama. Oleh karena itu di perlukan suatu notasiuntuk menyatakan waktu tempuh, sedemikian rupasehingga dapat berlaku di semua komputer. Maka kitaperlu menentukan pengkelasan fungsi ( classes offunction)

• Contoh berikut adalah, jika pada RAM menghasilkanwaktu tempuh (1) 10n3+5n2+7, kita tahu bahwa T(n)tersebut berada pada area kubik, dan jika komputerlain menghasilkan (2) 2n3+3n+79, hal ini seharusnyadapat di nyatakan juga berada dalam ranah kubik.

• Dengan demikian ( 1) dan ( 2) berada pada kelasyang sama. Oleh karena itu di perlukan suatu notasiuntuk menyatakan waktu tempuh, sedemikian rupasehingga dapat berlaku di semua komputer. Maka kitaperlu menentukan pengkelasan fungsi ( classes offunction)

CLASSES OF FUNCTION

• Asymptotic Notation merupakan notasi formaluntuk mengungkapkan mengani suatu fungsidan mengklasifikasikannya,

• Asymptotic Analysis adalah menganalisis danmengklasifikasikan suatu fungsi ke dalamnotasi asimptotik dan untukmengklasifikasikan notasi kita perlu fitur-fituruntuk melakukannya.

• Asymptotic Notation merupakan notasi formaluntuk mengungkapkan mengani suatu fungsidan mengklasifikasikannya,

• Asymptotic Analysis adalah menganalisis danmengklasifikasikan suatu fungsi ke dalamnotasi asimptotik dan untukmengklasifikasikan notasi kita perlu fitur-fituruntuk melakukannya.

Fitur Utama

• Bagaimana meletakan fungsi yang berbeda kedalam kelas yang sama, misal 10n3+5n2+17 dan2n3+3n+79 seharusnya berada dalam satu kelas.Sehingga pengali konstan (constant multiplier )harus diabaikan dalam kedua fungsi diatas.

• Notasi pada Class juga harus memperhatikanadanya kencenderungan nilai n ke arah tak hingga( n ) , sehingga kita juga harusmemperhatikan ukuran dan prilaku dari inputinstance n.

• Bagaimana meletakan fungsi yang berbeda kedalam kelas yang sama, misal 10n3+5n2+17 dan2n3+3n+79 seharusnya berada dalam satu kelas.Sehingga pengali konstan (constant multiplier )harus diabaikan dalam kedua fungsi diatas.

• Notasi pada Class juga harus memperhatikanadanya kencenderungan nilai n ke arah tak hingga( n ) , sehingga kita juga harusmemperhatikan ukuran dan prilaku dari inputinstance n.

Macam NA

• Ada 3 Notasi Asimtotik :• O (big oh atau order of)• Ω (omega)• Θ (theta)

• Ada 3 Notasi Asimtotik :• O (big oh atau order of)• Ω (omega)• Θ (theta)

Big Oh atau O

• Merupakan batas atas fungsi atau order waktuproses,

• g: N R+ adalah suatu fungsi• O(g(n)) merupakan kumpulan fungsi-fungsi

N R+ yang mempunyai batas atas g(n) untukn yang cukup besar.

• O(g(n)) = f(n)/(c R+ ) ( n N) f(n) ≤ c g(n), n ≥ N)

• Merupakan batas atas fungsi atau order waktuproses,

• g: N R+ adalah suatu fungsi• O(g(n)) merupakan kumpulan fungsi-fungsi

N R+ yang mempunyai batas atas g(n) untukn yang cukup besar.

• O(g(n)) = f(n)/(c R+ ) ( n N) f(n) ≤ c g(n), n ≥ N)

Big-Oh

contoh

• 1000 n2 O(n3) karena1000 n2 ≤ 1 x n3 untuk n ≥ 1000 1 = c, 1000 = N• 1000 n2 O(n2), Carilah c dan n1000 n2 O(n2)1000 n2 ≤ c n2

c = 10001000 n2 ≤ 1000 n2 , n ≥ 1

• 1000 n2 O(n3) karena1000 n2 ≤ 1 x n3 untuk n ≥ 1000 1 = c, 1000 = N• 1000 n2 O(n2), Carilah c dan n1000 n2 O(n2)1000 n2 ≤ c n2

c = 10001000 n2 ≤ 1000 n2 , n ≥ 1

contohApakah 5n + 10 O (n2) ?Ya, karena 5n + 10 < 5n2 + 10n2 = 15n2 untuk n > 1Jadi untuk c = 15, n0 = 1 |5n + 10| < c . |n2|

Jika L = 0, maka f(n) O(g(n))g(n) O(f(n))

Jika L 0, maka f(n) O (g(n))g(n) O (f(n))

Jika L = ,maka f(n) O (g(n))g(n) O (f(n))

Lngnf

n

lim

Apakah 5n + 10 O (n2) ?Ya, karena 5n + 10 < 5n2 + 10n2 = 15n2 untuk n > 1Jadi untuk c = 15, n0 = 1 |5n + 10| < c . |n2|

Jika L = 0, maka f(n) O(g(n))g(n) O(f(n))

Jika L 0, maka f(n) O (g(n))g(n) O (f(n))

Jika L = ,maka f(n) O (g(n))g(n) O (f(n))

Lngnf

n

lim

contoh

• f(n) = 3n2+5n+10• g(n)=n2 merupakan order atau batas atas untuk f(n)• g(n) f(n)• misal : 3g(n)=3n2 3n2+5n+10,• Bagaimana dengan (3+1)g(n)=4n2 ….…3n2+5n+10 4 n2

• dengan n10 dan 3n2+5n+10 4n2

n0 c• Jadi 3n2+5n+10 O(n2), karena untuk n 10 ,

3n2+5n+10 4n2

• f(n) = 3n2+5n+10• g(n)=n2 merupakan order atau batas atas untuk f(n)• g(n) f(n)• misal : 3g(n)=3n2 3n2+5n+10,• Bagaimana dengan (3+1)g(n)=4n2 ….…3n2+5n+10 4 n2

• dengan n10 dan 3n2+5n+10 4n2

n0 c• Jadi 3n2+5n+10 O(n2), karena untuk n 10 ,

3n2+5n+10 4n2

contoh

cnnn

nnn

0

00310531053lim 22

2

Karena,

))(()(0

))(()()()(lim

ngOnfc

ngOnfn ngnf

Karena,

Sehingga, 3n2+5n+10 O(n2)

Teorema Polinomial Dalam Notasi Oh

• Jika a0,a1,…,an adalah bilangan riil dengan an0maka f(x)=anxn+…+a1x+a0 adalah O(xn).

• Contoh :• Cari Order deret 1+2+3+…+n ?• Jawab :• 1+2+3+…+n = = ½ n2 + ½ n, sehingga Ordernya

adalah O(n2)

• Jika a0,a1,…,an adalah bilangan riil dengan an0maka f(x)=anxn+…+a1x+a0 adalah O(xn).

• Contoh :• Cari Order deret 1+2+3+…+n ?• Jawab :• 1+2+3+…+n = = ½ n2 + ½ n, sehingga Ordernya

adalah O(n2)

Teorema Logaritma Dalam Notasi Oh

• Jika b adalah bilangan riil > 1 maka :• blog x adalah O(xn) untuk semua bilangan

bulat n1• xn adalah O(bx) untuk semua ilangan bulat n0• x blog x adalah O(x2) x b

• Jika b adalah bilangan riil > 1 maka :• blog x adalah O(xn) untuk semua bilangan

bulat n1• xn adalah O(bx) untuk semua ilangan bulat n0• x blog x adalah O(x2) x b

Teorema Hirarki Dalam Notasi Oh

• Setiap fungsi merupakan big oh dari fungsikanannya :

• 1,2log(n),…., , , , n, n(2log (n)),n ,n2,n3,…,2n,n!,nn.

• Setiap fungsi merupakan big oh dari fungsikanannya :

• 1,2log(n),…., , , , n, n(2log (n)),n ,n2,n3,…,2n,n!,nn.

Teorema Lainnya Dalam Notasi Oh

• Jika f(n) =O(g(n)) dan c adalah konstanta makac f(n)=O(g(n))

• Jika f(n) =O(g(n)) dan h(n)= O(g(n)) makah(n)+f(n)=O(g(n))

• Jika f(n) =O(a(n)) dan g(n)= O(b(n)) makaf(n) g(n)=O(a(n) b(n))

• Jika a(n) =O(b(n)) dan b(n)= O(c(n)) makaa(n)=O(c(n))

• Jika f(n) =O(a(n)) dan g(n)= O(b(n)) makaf(n)+g(n)=O(max |a(n)|,|b(n)|)

• Jika f(n) =O(g(n)) dan c adalah konstanta makac f(n)=O(g(n))

• Jika f(n) =O(g(n)) dan h(n)= O(g(n)) makah(n)+f(n)=O(g(n))

• Jika f(n) =O(a(n)) dan g(n)= O(b(n)) makaf(n) g(n)=O(a(n) b(n))

• Jika a(n) =O(b(n)) dan b(n)= O(c(n)) makaa(n)=O(c(n))

• Jika f(n) =O(a(n)) dan g(n)= O(b(n)) makaf(n)+g(n)=O(max |a(n)|,|b(n)|)

contoh

• Nyatakan fungsi di bawah ini dalam notasi O :a. n+n(2 log n)b.c.

• Nyatakan fungsi di bawah ini dalam notasi O :a. n+n(2 log n)b.c.

)log(sin 23 nnn

153)log(21 2 nnn

jawab

Ω (omega)

• Merupakan kebalikan dari big Oh (Order)• Ω(g(n))=g(n) merupakan batas bawah fungsi-

fungsi f(n)• Ω (g(n)) = f(n)/(c R+ ) ( n N) f(n) ≥ c

. g (n), n ≥ N)

• Merupakan kebalikan dari big Oh (Order)• Ω(g(n))=g(n) merupakan batas bawah fungsi-

fungsi f(n)• Ω (g(n)) = f(n)/(c R+ ) ( n N) f(n) ≥ c

. g (n), n ≥ N)

))(()(0

))(()()()(lim

ngOnf

ngnfcn ng

nf

Omega

contoh

• Jadi dari contoh sebelumnya maka• 3n2+5n+10Ω(nn), tetapi 3n2+5n+10Ω(n2

log n), karena

• Jadi dari contoh sebelumnya maka• 3n2+5n+10Ω(nn), tetapi 3n2+5n+10Ω(n2

log n), karena

0000log10

log5

log3lim

log1053lim 22

2

nnnnnnnnn

nn

contoh• n3 ≥ 1000 n2 untuk n ≥ 1000

n3 Ω (1000 n2)• n3 ≥ n2 , n ≥ 1

n3 Ω (n2)• (n + 1)! = (n + 1) n! ≥ n! untuk n ≥ 1

(n + 1) ! Ω (n!)• 5000 n2 + 10000 n + 106 ≥ n2, untuk n ≥ 1

5000 n2 + 10000 n + 106 Ω (n2)5000 n2 + 10000 n + 106 O(n2)5000 n2 + 10000 n + 106 O (n2) Ω (n2)O (n2) Ω (n2)= (n2)

• n3 ≥ 1000 n2 untuk n ≥ 1000n3 Ω (1000 n2)

• n3 ≥ n2 , n ≥ 1n3 Ω (n2)

• (n + 1)! = (n + 1) n! ≥ n! untuk n ≥ 1(n + 1) ! Ω (n!)

• 5000 n2 + 10000 n + 106 ≥ n2, untuk n ≥ 15000 n2 + 10000 n + 106 Ω (n2)5000 n2 + 10000 n + 106 O(n2)5000 n2 + 10000 n + 106 O (n2) Ω (n2)O (n2) Ω (n2)= (n2)

jadi

Jika L = 0, maka f(n) Ω(g(n))g(n) Ω (f(n))

Jika L 0, maka f(n) Ω (g(n))g(n) Ω (f(n))

Jika L = , maka f(n) Ω (g(n))g(n) Ω (f(n))

50 n + 10 ln n Ω (ln n)n2 Ω (n3)

Lngnf

n

lim Jika L = 0, maka f(n) Ω(g(n))

g(n) Ω (f(n))Jika L 0, maka f(n) Ω (g(n))

g(n) Ω (f(n))Jika L = , maka f(n) Ω (g(n))

g(n) Ω (f(n))50 n + 10 ln n Ω (ln n)

n2 Ω (n3)

Θ (theta)

• Sehingga,• f(n) (g(n)) bila dan hanya bila f(n) O (g(n) Ω (g(n)))• f(n) mempunyai order yang sama dengan g(n)• f(n) (g(n) bila dan hanya bila g(n) (f(n)), f(n) berupa fungsi non

rekursif• Notasi Asimtotik digunakan untuk menentukan kompleksitas suatu

algoritma dengan melihat waktu tempuh algoritma. Waktu tempuhalgoritma merupakan

• fungsi : N → R+,

• Jadi• O(g(n))Ω(g(n))Θ(g(n)) maka,• f(n) Θ(g(n)) BILA DAN HANYA BILA (g(n)) Θ(g(n))

))(()()),(()())(())(())(()(

))(()()),(()(0

)()(lim

ngnfngOnfngngngOnfc

ngnfngOnf

ngnf

n

• Sehingga,• f(n) (g(n)) bila dan hanya bila f(n) O (g(n) Ω (g(n)))• f(n) mempunyai order yang sama dengan g(n)• f(n) (g(n) bila dan hanya bila g(n) (f(n)), f(n) berupa fungsi non

rekursif• Notasi Asimtotik digunakan untuk menentukan kompleksitas suatu

algoritma dengan melihat waktu tempuh algoritma. Waktu tempuhalgoritma merupakan

• fungsi : N → R+,

• Jadi• O(g(n))Ω(g(n))Θ(g(n)) maka,• f(n) Θ(g(n)) BILA DAN HANYA BILA (g(n)) Θ(g(n))

Theta

contoh

• 3n2+5n+10 Θ(n2)• 2n+1 Θ(22n) ???????? jawabannya adalah

BUKAN/TIDAK, karena

• Jadi 2n+1O(22n) tetapi 2n+1 Ω (22n)

022lim

222lim 2

nnn

n

n

• 3n2+5n+10 Θ(n2)• 2n+1 Θ(22n) ???????? jawabannya adalah

BUKAN/TIDAK, karena

• Jadi 2n+1O(22n) tetapi 2n+1 Ω (22n)

022lim

222lim 2

nnn

n

n