KOMPLEKSITAS WAKTU ASIMPTOTIK Anna Kurniawati
Jan 22, 2016
KOMPLEKSITAS WAKTU ASIMPTOTIK
Anna Kurniawati
Definisi : Notasi asimtotik merupakan himpunan
fungsi yang dibatasi oleh suatu fungsi n N yang cukup besar.
Fungsi : N → R (sering R+) Notasi Asimtotik digunakan untuk
menentukan kompleksitas suatu algoritma dengan melihat waktu tempuh algoritma. Waktu tempuh algoritma merupakan fungsi : N → R+
Kompleksitas Waktu Asimptotik
Kompleksitas Waktu Asimptotik
Terdapat tiga macam yaitu :• Keadaan terbaik (best case)
Dilambangkan dengan notasi (...) dibaca Theta
• Keadaan rata-rata (average case)Dilambangkan dengan notasi (...) dibaca Omega
• Keadaan terburuk (worst case)Dilambangkan dengan notasi O(...) dibaca Big-O
Kinerja sebuah algoritma biasanya diukur dengan menggunakan patokan keadaan terburuk (worst case) yang dinyatakan dengan Big-O
Notasi Big Oh
Definisi 1 : waktu terburuk
iff ada dua bilangan konstanta c dan no
Theorema : Misal
adalah suatu polinom derajat n. Maka
onnngcnf ,
01.... anananA mn
mnnA
ngnf
Notasi Theta
Definisi 2 : waktu tercepat
iff ada dua konstanta c dan no ngnf
onnngcnf ,
Notasi Omega
Definisi 3 : waktu rata-rata
iff ada tiga konstanta positif c1, c2, dan no ngnf
onnngcnfngc , 21
7
Contoh 3. Algoritma sequential search. procedure PencarianBeruntun(input a1, a2, ..., an : integer, x : integer, output idx : integer) Deklarasi k : integer ketemu : boolean { bernilai true jika x ditemukan atau false jika x tidak ditemukan } Algoritma: k 1 ketemu false while (k n) and (not ketemu) do if ak = x then ketemu true else k k + 1 endif endwhile { k > n or ketemu } if ketemu then { x ditemukan } idx k else idx 0 { x tidak ditemukan } endif
8
J u m l a h o p e r a s i p e r b a n d i n g a n e l e m e n t a b e l : 1 . K a s u s t e r b a i k : i n i t e r j a d i b i l a a 1 = x .
T m i n ( n ) = 1 2 . K a s u s t e r b u r u k : b i l a a n = x a t a u x t i d a k d i t e m u k a n .
T m a x ( n ) = n 3 . K a s u s r a t a - r a t a : J i k a x d i t e m u k a n p a d a p o s i s i k e - j , m a k a o p e r a s i
p e r b a n d i n g a n ( a k = x ) a k a n d i e k s e k u s i s e b a n y a k j k a l i .
T a v g ( n ) = 2
)1()1(2
1)...321(
n
n
nn
n
n
Fungsi Kompleksitas
MENGHITUNG WAKTU PROSES (1)
Contoh : Pseudocode Selection Sort (pseudocode 3.6)1 for i=1 to N-1 do2 min=i3 for j=i+1 to N do4 if A[j]<A[min] then5 min=j6 end if7 end for8 swap(A[i],A[min])9 end for
Hitung waktu proses algoritma yang diperlukan untuk mengurutkan deretan yang berisi 8 angka acak !
Bagaimana jika ukuran input belum diketahui? Dinyatakan dengan N Waktu proses dinyatakan dengan sebuah persamaan N, selanjutnya disebut
Fungsi Kompleksitas Fungsi Kompleksitas menyatakan seberapa kompleksnya sebuah algoritma
MENGHITUNG WAKTU PROSES (2) Asumsi bahwa nilai N belum diketahui Bisa dihitung bahwa untuk setiap
perulangan i akan terjadi perulangan j sebanyak N-1, N-2, N-3, ..., 1 kali
Misalkan nilai N adalah 5, berarti kita perlu menghitung 5+4+3+2+1 (rumus deret hitung)
Dengan nilai a dan b = 1 diperoleh :
))1(2(2
bNaN
DN
2
)1( NN
DN
FUNGSI KOMPLEKSITAS
Fungsi Kompleksitas algoritma Selection Sort di atas
Dengan rumus Fungsi Kompleksitas N(N+1)/2 berarti jika N=5 maka waktu proses adalah 15.
Jika nilai N diperbesar menjadi 8, maka waktu proses menjadi 36.
Nilai N dan waktu proses bisa dipetakan dalam sebuah koordinat Cartesius dengan N di sumbu x dan waktu proses di sumbu y.
Terlihat bahwa waktu proses algoritma Selection Sort bertumbuh (growth rate) secara linear.
2
)1()(
nnnf
MEMBACA BIG-OH
O(1) artinya algoritma konstan O(n) artinya algoritma linear O(n2) artinya algorritma quadratic O(n3) artinya algoritma qubic O(log n) contohnya pada full balanced Binary
Search Tree O(nm) artinya algoritma eksponensial Notasi Big-O bisa berisi kombinasi dari contoh di
atas Penyederhanaan Big-O dilakukan pada komponen
yang “less important”
LATIHAN
Hitunglah Fungsi Kompleksitas untuk algoritma bilangan Fibonacci