Friday, 26 December 2014

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(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.