Algoritma Efisiensi

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.       T_max(n) : kompleksitas waktu untuk kasus terburuk (worst case),

à kebutuhan waktu maksimum.

b.        T_min(n) : kompleksitas waktu untuk kasus terbaik (best case),

à kebutuhan waktu minimum.

c.       T_avg(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