Kompleksitas Algoritma Lanjut (Minggu 3)

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