Kompleksitas Algoritma

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

�  Apakah ada lingkaran dalam grafik

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

1. Asymptotic/theoretic/mathematic : berdasarkan pendekatan secara teori atau atas dasar analisa secara matematik
2. 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

�         Notasiasymptotic 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(n²).

�        Menggambarkan bagaimana fungsi f(n) tumbuh pd pembandingan untuk  n².

�         Mendefinisikan himpunan fungsi ;

�         Pada prakteknya untuk membandingan 2 ukuran fungsi.

�         Notasi menggambarkan perbedaan  rate-of-growth hubungan antara definisi fungsi dan definisi himpunan

�         fungsi.