Archive for November 2013
Efisiensi Algoritma
Analisa yang
paling sering dilakukan pada suatu algoritma adalah waktu proses. Menentukan
waktu proses secara tepat merupakan pekerjaan yang sangat sulit karena waktu
proses secata eksak sangat terhgantung pada implementasi algoritma dan
perangkat keras yang dipakai. Analisa yang di inginkan untuk menyatakan
efisiensi algoritma haruslah dibuat se umum mungkin sehingga bias dipakai
pada semua algoritma, terlepas dari implementasi dan juga compiler yang
di pakai maupun perangkat keras yang digunakan. Akbiatnya analisa tidak dipakai
pada waktu proses secata eksak. Kompleksitas algoritma cukup di nyatakan dalam
order waktu proses (Big-Oh) secara fungsi jumlah data masukan yang diberikan.
Dalam analisa tersebut kita menfokuskan diri pada operasi aktif yang merupakan
pusat algoritma, yaitu bagian algoritma yang paling sering di eksekusi.
Bagian-bagian lain seperti pemasukan data,penugasan (asigment), dan lain-lain
dapat diabaikan karena bagian-bagian tersebut tidak sesering operasi aktif. Jumlah
eksekusi operasi aktif itulah yang selanjutnya dihitung
Contoh
Perhatikan
potongan program beikut ini yang menghitung jumlah n buah suatu bilangan ril
Carilah operasi
aktif program tersebut dan nyatakan order waktu dalam proses sebagai fungsi
jumlah masukan (n)
Penyelesaian
Untuk mencari
operasi aktif, haruslah di tentukan beberapa kali program eksekusi pada
tiap-tiap bagian.
• Bagian a,
eksukusi satu kali
• Bagian b,
merupakan bagian loop, kalang itu akan dip roses berdasarkan kenaikan harga I
dari i=1 hingga i=n.jadi statement
sum=sum+v[i] akan dip roses sebanyak n kali sesuai dengan kenaikan harga
i
• Bagian c,
akan di proses sekali
Oleh karena
bagian b merupakan bagian yang paling sering dip roses, maka bagian b merupakan
operasi aktif. Bagian a dan c dapat diabaikan karena bagian-bagian tersebut
tidak dip roses sesering bagian b
Banyak kali
bagian b diproses sama dengan banyak data yang dimasukan (=n). dengan demikian,
program penjumlahan n buah bilangan rill memiliki order sebanding dengan n. dengan
kata lain program memiliki O(n).
Contoh 12.7
Carilah order
waktu proses bagian-bagian program berikut ini
a. for i=2 to n
A=2*n +i*n
End for
b. for i=1 to n
for j=1 to i
A=n+i*j
End for
End for i
c. for i=[n/2]
to n
A=n-1
End for i
Penyelesaian
Jumlah
penyelesaian statement A=a*n+1*n mengikuti iterasi dalam I, yaitu dari
i=2 hingga i=n. jadi sebanyak (n-2) + 1=(n-1) kali. Perhatikan bahwa yang
dipentingkan disini bukanlah berapa banyak nilai variable A tetapi frekuensi
pemrosesan A, jadi Algoritma memiliki order O(n)
Pada
I=1, j berjalan
1 hingga 1 sehingga A dip roses 1 kali
I=2, j berjalan
1 hingga 2 sehingga A dip roses 2 kali
I=3, j berjalan
1 hingga 3 sehingga A dip roses 3 kali
Dan seterusnya
I=n, j berjalan
1 hingga n sehingga A di proses sebanyak n kali
KOMPLEKSITAS
ALGORITMA
Sebuah pertanyaan yang sering muncul
adalah “Seberapa efisienkah suatu algoritma atau potongan kode?”
Efisiensi tergantung dari beberapa hal, diantaranya:
· Kinerja CPU
· Kinerja Memori
· Kinerja Disk
· Kinerja Jaringan
Semua aspek tersebut sangat penting, tapi makalah ini akan membahas mengenai poin pertama, yaitu CPU. Berhati-hatilah ketika membandingkan antara :
1. Performa: Berapa banyak waktu / memori / disk yang digunakan ketika program berjalan. Tergantung dari mesin, compiler, dan kode.
2. Kompleksitas: Apa yang akan terjadi ketika ukuran masalah semakin besar.
Kompleksitas memengaruhi performa, namun tidak sebaliknya. Waktu
yang diperlukan untuk melakukan suatu baris kode / algoritma sebanding dengan operasi dasar yang dilakukan.
Beberapa contoh operasi dasar :
· Satu operasi aritmatika (misal: +, *)
· Satu assignment
· Satu ekspresi (misal: x==0)
· Pembacaan input
· Penulisan output (primitif)Beberapa algoritma melakukan jumlah
operasi yang sama
dalam setiap kali pemanggilannya. Algoritma
seperti ini dikatakan memerlukan waktu yang konstan. Beberapa algoritma lain
melakukan jumlah operasi yang
berbeda, tergantung dari jumlah masukan pada parameter-nya.
Misalnya, algoritma pemanggilan berurutan (sequence), jumlah
operasi yang dilakukan tergantung dari jumlah pemanggilan. Parameter
yang nilainya memengaruhi
jumlah operasi yang dilakukan
disebut problem size atau input size.
Ketika kita mengukur kompleksitas suatu algoritma, kita bukan memerlukan jumlah operasi yang tepat, kita memerlukan bagaimana hubungan antara
jumlah operasi tersebut dengan ukuran masalah (problem size). Jika
problem size-nya double, apakah jumlah operasi akan tetap dua
kali lipat? Ataukah bekembang dengan cara tertentu? Untuk algoritma yang
memerlukan waktu yang konstan, melipatgandakan ukuran masalah tidak
memengaruhi jumlah operasi yang dilakukan. Lebih jauh lagi, biasanya kita tertarik dengan worst case,
atau kasus terburuk; yaitu jumlah operasi terbanyak yang mungkin dilakukan sebuah algoritma untuk ukuran masalah yang diberikan (selain
itu, terdapat juga kasus rata-rata –average case- dan kasus terbaik –best
case-)
MODEL PERHITUNGAN KEBUTUHAN WAKTU/RUANG
Waktu/Ruang
• Kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang
dieksekusi.
• Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi
tertentu, maka kita dapat menghitung berapa waktu sesungguhnya
untuk melaksanakan algoritma tersebut.
>>> Tipe data yang digunakan adalah :
- integer
- real
- real
Dua nilai yang sama dengan operator yang sama tetapi dengan
variabel yang berbeda, maka terdapat perbedaan kecepatan /
proses penyelesaiannya.
Contoh :
à 250 + 17 = 267 (lebih cepat dari)
à 250 + 17 = 267 (lebih cepat dari)
à 250.0 + 17.0 = 0.25*103 + 0.17*102
= 0.25*103 + 0.017*103
= (0.25+ 0.017)*103
= 0.267*103
= 267.0
= 0.25*103 + 0.017*103
= (0.25+ 0.017)*103
= 0.267*103
= 267.0
