ALGORITMA EFISIENSI
1. Algoritma
Algoritma adalah sekumpulan instruksi yang
dijalankan secara berurutan untuk melakukan perhitungan komputerisasi serta
untuk memecahkan masalah. Sebuah
algoritma tidak saja harus benar, tetapi juga harus efisien. Algoritma
yang bagus adalah algoritma yang efektif dan efisien. Algoritma yang efektif
diukur dari berapa jumlah waktu dan ruang (space) memori yang dibutuhkan
untuk menjalankannya. Algoritma yang efisien adalah algoritma yang
meminimumkan kebutuhan waktu dan ruang. Kebutuhan waktu dan ruang suatu
algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah
data yang diproses. Keefektifan algoritma dapat digunakan untuk menilai
algoritma yang bagus.
2. Jenis
Algoritma
Terdapat beragam klasifikasi algoritma
dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk
melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan dan metode yang digunakan untuk mendesain
algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu
algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan
dalam banyak algoritma yang berbeda.
- Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
- Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumbang tindih. Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
- Metode serakah. Sebuah algoritma serkah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
3. Kompleksitas
Algoritma
Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma
tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat
menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas
yang rendah, sementara algoritma yang membutuhkan waktu lama untuk
menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas
ruang.
· Kompleksitas
waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan
untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n.
Kompleksitas
waktu dibedakan atas tiga macam :
a. Tmax(n)
: kompleksitas waktu untuk kasus terburuk (worst
case),
à
kebutuhan waktu maksimum.
b. Tmin(n)
: kompleksitas waktu untuk kasus terbaik (best
case),
à
kebutuhan waktu minimum.
c. Tavg(n):
kompleksitas waktu untuk kasus rata-rata (average
case)
à
kebutuhan waktu secara rata-rata
· Kompleksitas
ruang, S(n), diukur dari memori yang digunakan oleh struktur data
yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
Dengan
menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu (ruang) yang
diperlukan algoritma dengan meningkatnya ukuran masukan n.
4. Efisiensi
Algoritma
Efisiensi
algoritma dapat ditinjau dari dua hal yaitu kecepatan(waktu) dan space
memori.
Faktor-faktor yang mempengaruhi :
a. Kecepetan
· Banyak
langkah
Banyak
langkah dalam suatu algoritma dinyatakan dengan banyaknya operasi aritmatika
dan logika yang dilakukan. Dengan
demikian hal ini bergantung pada statement dan
jenis algoritma :
-
sequensial
-
branching
-
looping
-
subroutine
call (bisa memanggil prosedur dan bisa memanggil fungsi)
· Tipe
data
-
Integer
-
real
Dua
nilai yg sama dgn operator yg sama tapi dgn variabel yg berbeda, maka terdapat
perbedaan kecepatan/proses penyelesaiannya.
· Operator-operator
Urutan penggunaan operator/penempatan operator bisa
mempengaruhi efisiensi.Contoh
perkalian (*) lebih lama daripada penjumlahan (+)
Operator
aritmatika : +,-,*,/,^,div,mod
Operator logika : AND,OR,NOT masing-masing
1.
Operator adalah jika hasil perhitungannya
termasuk dalam himpunan itu sendiri.
2 < 5 à bukan operator tapi
konstanta logika karena tidak menghasilkan nilai yang sejenisOperator : H x H à H
b. Space
memory
· Alokasi
memori
Berkaitan dengan struktur data dinais, procedure/function call
dan recursif