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

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