Analisis Algoritma

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.

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

KLASIFIKASI ALGORITMA

·        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:

Loop luar dieksekusi n kali

Loop dalam dieksekusi m kali

Total eksekusi = n × m kali

·        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:

aktu 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:

a[i,j] akan dieksekusi sebanyak (m x n) kali.

Jadi T(n) = O(n2)

3. Consecutive Statement (statement yang berurutan)

·        Untuk statement yang berurutan, waktu eksekusinya adalah jml dari masing-masing statement.

·        Berdasarkan pengertian Big-OH, hal tsb akan diambil nilai yang terbesar.

Contoh:

 Jadi T(n) = T1(n) + T2(n) = O(n2)

4. if else

Total waktu eksekusi adalah waktu test ditambah waktu yang terbesar dari eksekusi Statemen1 atau Statemen2

Contoh:

Jadi total waktu eksekusi adalah 1 + 10 = 11

Jadi T(n) = O(n)

LATIHAN

• Sebuah algoritma tidak hanya harus benar, tetapi juga harus mangkus (efficient)

• Ukuran kemangkusan algoritma: waktu dan ruang memori (space).

• Algoritma yang mangkus: algoritma yang meminimumkan kebutuhan waktu dan ruang

TIPE-TIPE PROBLEM

• Sorting

• Searching

• String processing

•Graph problem

• Combinatorial problem

• Geometric Problem

• Numerical Problem

Daftar Pusaka

www.scribd.com

www.analisisalgoritma.com

www.ftikugm.co.id

www.ftik.itb.com