ANALISIS ALGORITMA

No Comments



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

Dear readers, after reading the Content please ask for advice and to provide constructive feedback Please Write Relevant Comment with Polite Language.Your comments inspired me to continue blogging. Your opinion much more valuable to me. Thank you.