Sinau Online: ANALISIS ALGORITMA

- Algoritma adalah urutan langkah yang tepat dan pasti dalam memecahkan suatu masalah secara logis.

- Beberapa masalah dapat diselesaikan dengan algoritma yang bermacam macam asal hasilnya sama.

- Setiap bahasa pemrograman memiliki kelebihan dan kekurangan dalam mengimplementasikan algoritma dan setiap pemrogram dapat mengimplementasikan suatu algoritma dengan cara yang berbeda-beda pula.

- Namun algoritma dapat dianalisis efisiensi dan kompleksitasnya.

- Penilaian algoritma didasarkan pada:

· Waktu eksekusi (paling utama)

· Penggunaan memori/sumber daya

· Kesederhanaan dan kejelasan algoritma

- Analisis algoritma tidak mudah dilakukan secara pasti, maka hanya diambil:

· Kondisi rata-rata (average case)

· Kondisi terburuk (worst case)

- Waktu eksekusi dipengaruhi oleh:

· Jenis data input

· Jumlah data input

· Pemilihan instruksi bahasa pemrograman

- Faktor-faktor yang menyulitkan analisis disebabkan oleh:

· Implementasi instruksi oleh bahasa pemrograman yang berbeda

· Ketergantungan algoritma terhadap jenis data

· Ketidakjelasan algoritma yang diimplementasikan

- Langkah-langkah analisis algoritma

· Menentukan jenis/sifat data input.

· Mengidentifikasi abstract operation dari data input.

· Menganalisis secara matematis untuk menentukan average case atau worst case nya.

NOTASI Big-Oh

adalah fungsi yang lebih berkaitan dengan kelajuan proses daripada kelajuan pertambahan data.

T(n) = O(f(n))

jika ada konstan c dan no sedemikian rupa sehingga

T(n) ≤ c.f(n) untuk n ≥ no

Secara sederhana dikatakan bahwa O(f(n)) dpt dianggap sebagai nilai maksimum dari c.f(n).

Contoh:

Jika f(n) = 2n2 maka T(n) = O(n2)

Jika f(n) = 4n2 + 7n + 3 maka T(n) = O(n2)

Contoh program:

Penghitungan eksekusi:

˚ sum = 0 dieksekusi 1 kali

˚ i = 0 dieksekusi 1 kali

˚ i < n diekseklusi n kali

˚ i++ dieksekusi n kali

˚ sum = sum + a[i] dieksekusi n kali

----------------------

2 + 3n kali

Jadi T(n) = O(n)

Contoh program:

Penghitungan eksekusi:

- sum = 0 dieksekusi 1 kali

- i = 0 dieksekusi 1 kali

- i < n dieksekusi 1 kali

- i++ dieksekusi n kali

- j = o dieksekusi n kali

- j < n dieksekusi n × n kali

- j++ dieksekusi n × n kali

- sum = sum + a[ j ] dieksekusi n × n kali

---------------------------

3 + 2n + 3n2 kali

Jika sebagian besar instruksi pada program hanya dieksekusi constant kali.
Bersifat konstan, tidak bergantung pada parameter atau banyak data yang diolah
Merupakan algoritma paling ideal

Contoh:

Waktu eksekusinya sebanding/sama dengan jumlah data.
Setiap data input hanya diolah secara sederhana. Misal hanya di tambah,

dikurangi, dikalikan, dan dibagi.
Inilah kondisi optimal yang dicari dalam membuat algoritma.

Contoh :

Waktu eksekusi berbading dengan kwadrat jumlah data. Misal:

· Jika n=10 waktu eksekusinya 100

· Jika n=20 waktu eksekusinya 400

Biasanya timbul karena setiap data dieksekusi 2 kali, misal dlm nested loop.

Contoh : Algoritma Bublesort

Contoh:

Waktu eksekusi sebanding dengan logaritma dari jumlah data.
Misal jumlah data menjadi 2 kali semula berarti waktu proses bertama 1 unit, jika 1000 kali bertambah 10 unit, jika sejuta berarti 20 satuan.
Biasanya untuk algoritma yang memecah masalah besar kedalam sub masalah yang lebih kecil.
Contoh : Algoritma binary search dan algoritma fungsi rekursif

Bersifat linieritmis (linier dan logaritmis)
Untuk algoritma yang memecah masalah besar menjadi sub-masalah yang lebih kecil dan diselesaikan secara terpisah, kemudian hasilnya digabungkan.
Contoh : Quicksort

Untuk algoritma yang mengolah setiap data input 3 kali. Biasanya berupa 3 buah nested loop.

Algoritma semacam ini sebisa mungkin dihindari.

Contoh:

Pada implementasinya, algoritma kadang-kadang memiliki Big-Oh yang merupakan kombinasi dari klasifikasi dasar tersebut.
Perancangan algoritma yang memiliki Big-Oh baik tetapi rumit tidak selalu menguntungkan apabila jumlah data inputnya hanya sedikit.
Nilai Big-Oh adalah nilai worst case, sehingga dalam implementasinya biasanya tidak mencapai nilai setinggi itu.

CONTOH DAN ATURAN

1. For loop (perulangan)

Waktu eksekusi pada for loop, maksimum sebanyak waktu eksekusi statement-statement yang ada di dalam loop dikalikan banyaknya iterasi.

Contoh:

Waktu eksekusi = 2 x n kali

Jadi T(n) = O(n)

2. Nested for loop (perulangan bersarang)

· Dianalisis dari loop terdalam kemudian keluar.

· Waktu eksekusi total sebuah statement adalah waktu eksekusi statement tsb dikalikan hasil kali dari banyaknya iterasi semua loop yang ada diluarnya.

Contoh: