kompleksitas algoritma lanjut (minggu 3).ppt
TRANSCRIPT
-
KOMPLEKSITAS WAKTU ASIMPTOTIKAnna 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 AsimptotikTerdapat 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-OKinerja 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 : Misaladalah suatu polinom derajat n. Maka
-
Notasi Theta Definisi 2 : waktu tercepat iff ada dua konstanta c dan no
-
Notasi Omega Definisi 3 : waktu rata-rata
iff ada tiga konstanta positif c1, c2, dan no
-
*
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
-
*Fungsi Kompleksitas
Jumlah operasi perbandingan elemen tabel:
1. Kasus terbaik: ini terjadi bila a1 = x.
Tmin(n) = 1
2. Kasus terburuk: bila an = x atau x tidak ditemukan.
Tmax(n) = n
3. Kasus rata-rata: Jika x ditemukan pada posisi ke-j, maka operasi perbandingan (ak = x)akan dieksekusi sebanyak j kali.
Tavg(n) =
_1124438426.unknown
- 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]
-
MENGHITUNG WAKTU PROSES (2)Asumsi bahwa nilai N belum diketahuiBisa dihitung bahwa untuk setiap perulangan i akan terjadi perulangan j sebanyak N-1, N-2, N-3, ..., 1 kaliMisalkan nilai N adalah 5, berarti kita perlu menghitung 5+4+3+2+1 (rumus deret hitung)
Dengan nilai a dan b = 1 diperoleh :
-
FUNGSI KOMPLEKSITASFungsi 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.
-
MEMBACA BIG-OHO(1) artinya algoritma konstanO(n) artinya algoritma linearO(n2) artinya algorritma quadraticO(n3) artinya algoritma qubicO(log n) contohnya pada full balanced Binary Search TreeO(nm) artinya algoritma eksponensialNotasi Big-O bisa berisi kombinasi dari contoh di atasPenyederhanaan Big-O dilakukan pada komponen yang less important
-
LATIHANHitunglah Fungsi Kompleksitas untuk algoritma bilangan Fibonacci