BAB 2
Kompleksitas
Algoritma
Jenis algoritma
•
Divide and conquer : menyederhanakan problem yang besar.
•
Greedy methode : mencari yang optimal pada saat itu.
Algoritma :
jumlah langkah yang berhingga (finite) instruksinya jelas
Contoh : for i
do 10 then .....
Tujuan Menganalisis Algoritma
•
Efisiensi waktu
•
Efisiensi storage
Analisis algoritma
ü Menentukan
karakteristik kinerja (memprediksi sumber daya)
ü Mengapa ?
ü Memilih
algoritma yang paling efisien dari beberapa alternatif penyelesaian untuk kasus
yang sama
ü Mencari waktu
yang terbaik untuk keperluan praktis
ü Apakah algoritma
itu optimal untuk beberapa kasus atau ada yang lebih baik
Runing time
•
fungsi dari input size
•
Memanggil instruksi sederhana dan mengakses ke memory
word sebagai “primitive operation” atau “step”
•
Jumlah step eksekusi algoritma pada input tersebut
•
Dikenal juga “complexity and input”
Kompleksitas tergantung
Ø Ukuran input à bergantung pada problem
Ø Misalkan jumlah
data yang diurutkan
Ø Karakter lain
dari input
Ø Apakah data
sudah terurut
Kompleksitas
•
Worst-case : kompleksitas waktu untuk waktu terburuk (waktu tempuh bernilai
maksimum dari suatu fungsi f(n)) atau Tmax(n)
•
Best-case : kompleksitas waktu untuk waktu terbaik (kompleksitas waktu yang
bernilai minimum dari suatu fungsi f(n)) atau Tmin(n)
•
Average-case : kompleksitas waktu untuk kasus rata-rata
Metode
Analisis
- Asymptotic/theoretic/mathematic
: berdasarkan pendekatan
secara teori atau atas dasar analisa secara matematik
- Empirical/Practical/Empiris/Praktis : berdasarkan pendekatan praktis yang
biasanya didasarkan atas data-data yang telah ada atau data-data yang
di-generete / dibangkitkan
Asymptotic
•
Menggambarkan
karakteristik/perilaku suatu algoritma pada batasan tertentu (berupa suatu
fungsi matematis)
•
Dituliskan
dengan notasi matematis yg dikenal dgn notasi asymptotic
•
Notasi
asymptotic dapat dituliskan dengan beberpa simbul berikut
- Q, O, W, o,
w
Notasi
Asymptotic
- Q, O, W, o,
w
•
Didefinisikan
untuk fungsi diatas nilai biasa
–
Contoh: f(n) = Q(n2).
–
Menggambarkan
bagaimana fungsi f(n) tumbuh pd pembandingan untuk n2.
•
Mendefinisikan
himpunan fungsi ;
•
Pada
prakteknya untuk membandingan 2 ukuran fungsi.
•
Notasi
menggambarkan perbedaan rate-of-growth hubungan antara definisi
fungsi dan definisi himpunan
•
fungsi.