Yosh, sekedar menambah materi tentang cara mencari Kompleksitas Algoritma Nilai Asimtotik Menggunakan O-notation, Omega-notation, dari suatu algoritma dan berikut penjelasannya.
Mencari
T(n)
C(n)
Output = 3n+1 misal A
Input = 2 misal B
And = N misal C
< = N misal
D
<> = N misal
E
← = 3n+1 misal F
Maka hasil dari T(n) adalah sebagai berikut:
Maka hasil dari T(n) adalah sebagai berikut:
T(n) = (3n+1)A + 2B + (n)C + (n)D + (n)E + (3n+1)F
Mencari
O-nation
T(n) ϵ
O(g(n))
jika
T(n) ≤ c.g(n)
jika
T(n) ≤ c.g(n)
T(n) ≤ c.g(n) = (3n+1)+2+(n)+(n)+(n)+(3n+1)
≤ c.g(n)
pengecekan jika n =1, c = 13
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ 13.1
= (3*1+1)+2+(1)+(1)+(1)+(3*1+1) ≤ 13.1
= 4+2+1+1+1+4 ≤ 13
= 13 ≤ 13
Kondisi pengecekan menggunakan n = 1 dan c = 13 ternyata benar.
pengecekan jika n =1, c = 13
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ 13.1
= (3*1+1)+2+(1)+(1)+(1)+(3*1+1) ≤ 13.1
= 4+2+1+1+1+4 ≤ 13
= 13 ≤ 13
Kondisi pengecekan menggunakan n = 1 dan c = 13 ternyata benar.
Pengecekan
Lain
T(n) ≤ c.g(n^2) = (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ c.g(n^2)
pengecekan jika n = 24
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ 1*24^2
= (3*24+1)+2+24+24+24+(3*24+1) ≤ 1*24^2
= 73 + 2 +24 +24 +24 +73 ≤ 1*24^2
= 220 ≤ 576
maka jika n = 20 atau lebih maka hasilnya akan benar.
Mencari Omega-notation
T(n) ≤ c.g(n^2) = (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ c.g(n^2)
pengecekan jika n = 24
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≤ 1*24^2
= (3*24+1)+2+24+24+24+(3*24+1) ≤ 1*24^2
= 73 + 2 +24 +24 +24 +73 ≤ 1*24^2
= 220 ≤ 576
maka jika n = 20 atau lebih maka hasilnya akan benar.
Mencari Omega-notation
T(n) ϵ Ω(g(n))
jika
T(n) ≥ c.g(n)
T(n) ≥ c.g(n) = (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ c.g(n)
pengecekan jika n = 1 dan c = 1
jika
T(n) ≥ c.g(n)
T(n) ≥ c.g(n) = (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ c.g(n)
pengecekan jika n = 1 dan c = 1
= (3n+1)+2+(n)+(n)+(n)+(3n+1)
≥ 1.1
= (3*1+1)+2+1+1+1+(3*1+1) ≥ 1.1
= 4 + 2 + 1 + 1 + 1 + 4 ≥ 1
= 13 ≥ 1
Kondisi pengecekan menggunakan n = 1 dan c = 1 ternyata benar.
Pengecekan Lain
= (3*1+1)+2+1+1+1+(3*1+1) ≥ 1.1
= 4 + 2 + 1 + 1 + 1 + 4 ≥ 1
= 13 ≥ 1
Kondisi pengecekan menggunakan n = 1 dan c = 1 ternyata benar.
Pengecekan Lain
T(n) ≥ c.g(n) = (3n+1)+2+(n)+(n)+(n)+(3n+1)
≥ c.g(n)
pengecakan jika n = 2 dan c=1
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ 1.2
= (3*2+1)+2+2+2+2+(3*2+1) ≥ 1.2
= 7 + 2 + 2 + 2 + 2 + 7 ≥ 2
= 22 ≥ 2
Kondisi pengecekan menggunakan n = 2 dan c = 1 ternyata benar.
Pengecekan Lain
pengecakan jika n = 2 dan c=1
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ 1.2
= (3*2+1)+2+2+2+2+(3*2+1) ≥ 1.2
= 7 + 2 + 2 + 2 + 2 + 7 ≥ 2
= 22 ≥ 2
Kondisi pengecekan menggunakan n = 2 dan c = 1 ternyata benar.
Pengecekan Lain
T(n) ≥ c.g(n) = (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥
c.g(n)
pengecakan jika n = 15 dan c = 1
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ 1.2
= (3*15+1)+2+15+15+15+(3*15+1) ≥ 1.15
= 46 + 2 + 15 + 15 + 15 + 46 ≥ 15
= 139 ≥ 15
Kondisi pengecekan menggunakan n = 15 dan c = 1 ternyata benar.
maka sudah pasti jika :
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^0)
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^-1)
:
:
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^-n)
itu adalah benar.
Theta-notation
T(n) ϵ ϴ(g(n))
pengecakan jika n = 15 dan c = 1
= (3n+1)+2+(n)+(n)+(n)+(3n+1) ≥ 1.2
= (3*15+1)+2+15+15+15+(3*15+1) ≥ 1.15
= 46 + 2 + 15 + 15 + 15 + 46 ≥ 15
= 139 ≥ 15
Kondisi pengecekan menggunakan n = 15 dan c = 1 ternyata benar.
maka sudah pasti jika :
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^0)
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^-1)
:
:
T(n) ≥ c.g(n) = (2n+1)+3+(9n)+(n)+(n)+(n) ≥ c.g(n^-n)
itu adalah benar.
Theta-notation
T(n) ϵ ϴ(g(n))
jika
c2.g(n)
≤ T(n) ≤ c1.g(n)
