Halo, kembali lagi dengan kami setelah sebelumnya membahas Kompleksitas Algoritma : Percabangan dan untuk kali ini kita masih membahas kompleksitas algoritma, yaitu nilai asimtotik. Langsung saja disimak.
- Nilai asimtotik dari algoritma S = 1 - 2/3 + 3/6 - 4/10 + .....
Dari algoritma yang sudah didapat di post sebelumnya. Kita cari nilai asimtotiknya dengan cara mencari O (big oh), Ω (big omega), ϴ (big theta). T(n) dari algoritma S = 1 - 2/3 + 3/6 - 4/10 + .... adalah T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1.
O-notation
T(n) ϵ O(g(n))
jika
T(n) ≤ c.g(n)
T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≤ c.g(n)
Lakukan pengecekkan, jika n = 1 dan c = 7, maka
(1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≤ 7. 1
7 ≤ 7
Kondisi pengecekkan benar, maka n = 1 dan c = 7
T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≤ c.g(n^2)
Lakukan pengecekan, jika n = 10, maka
(10 - 2) + 10 + 3 + (10 - 2) + 1 + 10 + 10 + 1 + 1 ≤ 1. 10^2
52 ≤ 100
Lakukan pengecekan satu kali lagi dengan n = 100, maka
(100 - 2) + 100 + 3 + (100 - 2) + 1 + 100 + 100 + 1 + 1 ≤ 1. 100^2
502 ≤ 10000
Karena pengecekkan bernilai benar, untuk mengetahui nilai n dari n berapa ketika dilakukan pengecekkan sudah bernilai benar. Kita cari lagi n nya dengan n = 5.
(5 - 2) + 5 + 3 + (5 - 2) + 1 + 5 + 5 + 1 + 1 ≤ 1. 5^2
24 ≤ 25
Pengecekkan bernilai benar, maka c = 1; n = 5 dan T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n)). Karena T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n)) maka dapat diasumsikan bahwa T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n^2)), n^3 hingga n^n adalah anggota dari O.
Omega-notation
T(n) ϵ Ω(g(n))
jika
T(n) ≥ c.g(n)
T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≥ c.g(n)
Lakukan pengecekkan dengan n = 1 dan c = 1, maka
(1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≥ 1. 1
7 ≥ 1
Kondisi pengecekkan benar, cek lagi dengan mengubah n nya menjadi n = 2, maka
(2 - 2) + 2 + 3 + (2 - 2) + 1 + 2 + 2 + 1 + 1 ≥ 1. 2
12 ≥ 2
Kondisi benar, maka kita lakukan pengecekkan lagi dengan mengecek apakah T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n^0))
T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≥ c.g(n^0)
Lakukan pengecekkan dengan c = 1 dan n = 1, maka
(1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≥ 1. 1
7 ≥ 1
Kondisi pengecekkan benar, maka dapat diasumsikan bahwa T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ Ω(g(n^0)), n^-1, n^-n.
Theta-notation
T(n) ϵ ϴ(g(n))
jika
c2.g(n) ≤ T(n) ≤ c1.g(n)
Untuk mencari apakah T(n) ϵ ϴ(g(n)), ada cara termudahnya yaitu dengan melihat apakah O-notation dan Omega-notation menjadi anggota yang sama dalam satu g(n)? Untuk kasus ini, kita memiliki g(n) yang sama antara O dan Ω yaitu g(n), maka T(n) ϵ ϴ(g(n)). Kenapa dapat disimpulkan seperti itu? Karena Big Theta hanya akan menjadi salah satu anggota n. Maka dari itu, dapat disimpulkan seperti itu. Jika tidak percaya kalian bisa membuktikannya sendiri.
2. Dalam Algoritma sederhana sebelumnya Di No 2 di peroleh T(n) = 1 + 2 + … + n. , maka untuk menentukan notasi O, Omega , dan Theta nya sebagai berikut
2. Dalam Algoritma sederhana sebelumnya Di No 2 di peroleh T(n) = 1 + 2 + … + n. , maka untuk menentukan notasi O, Omega , dan Theta nya sebagai berikut
Jawab:
1 + 2 + … + n = O(n2) karena
1
+ 2 + … + n <= n
+ n + … + n = n2 untuk n >= 1.
1 + 2 + … + n = Omega(n) karena
1 + 2 + … + n <= 1 + 1 + … + 1 = n untuk n >= 1.
1 + 2
+ … + n >= [n/2] + … + (n
– 1) + n
>= [n/2] + … + [n/2] + [n/2]
= [(n + 1)/2] [n/2]
>= (n/2)(n/2)
= n2/4
Kita menyimpulkan bahwa
1 + 2
+ … + n = Omega(n2)
Oleh karena itu,
1 + 2
+ … + n = Theta(n2)
3.Nilai Asimtotik dari Algoritma Binary Search(No.3)
Bila Algoritma Binary Search mempunyai T(n) = 4 + n Maka, nilai asimtotiknya adalah sebagi berikut :
O-notation
3.Nilai Asimtotik dari Algoritma Binary Search(No.3)
Bila Algoritma Binary Search mempunyai T(n) = 4 + n Maka, nilai asimtotiknya adalah sebagi berikut :
O-notation
T(n) ϵ O(g(n))
jika
T(n) ≤ c.g(n)
4 + n ≤ c.g(n)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5 (terpenuhi)
4 + n ≤ c.g(n^2)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5 (terpenuhi)
2 kali terpenuhi sampai mana pun akan terpenuhi.
Contoh kedua
4 + n ≤ c.g(n)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 50 (terpenuhi)
4 + n ≤ c.g(n^2)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 500 (terpenuhi)
Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Oh.
Omega-notation
4 + n ≤ c.g(n)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5 (terpenuhi)
4 + n ≤ c.g(n^2)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5 (terpenuhi)
2 kali terpenuhi sampai mana pun akan terpenuhi.
Contoh kedua
4 + n ≤ c.g(n)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 50 (terpenuhi)
4 + n ≤ c.g(n^2)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 500 (terpenuhi)
Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Oh.
Omega-notation
T(n) ϵ Ω(g(n))
jika
T(n) ≥ c.g(n)
4 + n ≥ c.g(n)
Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1 (terpenuhi)
4 + n ≥ c.g(n^0)
Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1 (terpenuhi)
Contoh kedua
4 + n ≥ c.g(n)
Bila mana n=10 dan c=1
4 + n ≥ 1.10
14 ≥ 10 (terpenuhi)
4 + n ≥ c.g(n^0)
Bila mana n=10 dan c=1
4 + n ≥ 1.1
14 ≥ 1 (terpenuhi)
Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Omega.
4 + n ≥ c.g(n)
Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1 (terpenuhi)
4 + n ≥ c.g(n^0)
Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1 (terpenuhi)
Contoh kedua
4 + n ≥ c.g(n)
Bila mana n=10 dan c=1
4 + n ≥ 1.10
14 ≥ 10 (terpenuhi)
4 + n ≥ c.g(n^0)
Bila mana n=10 dan c=1
4 + n ≥ 1.1
14 ≥ 1 (terpenuhi)
Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Omega.
EmoticonEmoticon