ALGORITMA DAN KOMPLEKSITAS (lanjutan kompleksitas waktu)

KOMPLEKSITAS WAKTU

Contoh 1.
Tinjau algoritma menghitung rerata sebuah larik (array).
sum ←0 for i ←1 to n do
sum ← sum + a[i] endfor rata_rata ← sum/n

 Operasi yang mendasar pada algoritma tersebut adalah operasi penjumlahan elemen-elemen ai (yaitu sum←sum+a[i]) yang dilakukan sebanyak n kali.
 Kompleksitas waktu: T(n) = n.

 Kompleksitas waktu algoritma dihitung berdasarkan jumlah operasi perbandingan elemen larik (A[i] > maks).  

Kompleksitas waktu CariElemenTerbesar :  T(n) = n – 1. 

Kompleksitas waktu dibedakan atas tiga macam :

 1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case),        

→ kebutuhan waktu maksimum.

 2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case),        

→ kebutuhan waktu minimum. 

3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case)    

→ kebutuhan waktu secara rata-rata  

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.   

1. Kasus terbaik Tmin(n) = 1  

2. Kasus terburuk:  

  Tmax (n) = 2log n