GC _ Algorithmic Efficiency

Algorithmic Efficiency

• Algoritma

 Diagram Alur sering digunakan untuk menggambarkan sebuah algoritma.
Algoritma adalah sekumpulan berhingga dari instruksi-instruksi untuk melakukan perhitungan/ komputasi atau memecahkan suatu 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.

Seringkali dalam matematika dan komputasi, algoritma atau algoritme merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
Sedangkan pengertian desain adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
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.
Asal  usul  kata  algoritma  dapat  Anda  baca  dalam  buku  “The  Art  of  Computer Programming Second Edition Volume I” yang ditulis oleh Donald E. Knuth (1973, p1- )



Menurut  Donald  E.  Knuth  (1973,p4),  algoritma  dalam  penger tian  modern mempunyai kemiripan dengan istilah resep ,  proses, metode, teknik, prosedur, rutin . Algor itma  adalah  sekumpulan  aturan-aturan  berhingga  yang  memberikan  sederetan operasi-operasi untuk menyelesaikan suatu jenis masalah yang khusus. Menurut  Rinaldi  Munir,  algoritma  adalah  urutan  langkah-langkah  logis penyelesaian masalah yang disusun secara sistematis. Berdasarkan dua pengertian algoritma di atas, dapat disimpulkan bahwa algor itma merupakan suatu istilah yang luas, yang tidak hanya berkaitan dengan dunia komputer.
Sebenarnya kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan. Masalah timbul pada saat akan menuangkan bagaimana proses yang harus dilalui dalam suatu/sebuah sistem (program) bagi komputer sehingga pada saat eksekusinya, komputer dapat bekerja seperti yang diharapkan. Programer komputer akan lebih nyaman menuangkan prosedur komputasinya atau urutan langkah proses dengan terlebih dahulu membuat gambaran (diagram alur) diatas kertas.


• Berbagai Jenis Algoritma
Ada berbagai ragam klasifikasi algoritma dan setiap klasifikasi berbeda dan mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma 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 tumpang 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 serakah 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


• Kompleksitas Algoritma
Model abstrak pengukuran waktu/ruang harus independent dari pertimbangan mesin dan compiler apapun. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma. 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 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.
Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n. Dalam praktek, kompleksitas waktu dihitung berdasarkan jumlah operasi abstrak yang mendasari suatu algoritma, dan memisahkan analisisnya dari implementasi. Tinjau algoritma menghitung rerata pada Contoh 1. Operasi yang mendasar pada algoritma tersebut adalah operasi penjumlahan elemen-elemen ak (yaitu jumlah jumlah+ak). Kompleksitas waktu HitungRerata adalah T(n) = n.


• Algoritma yang Efisien
Algoritma yang efisien adalah algoritma yang meminimumkan kebutuhan ruang dan waktu. Efisiensi algoritma dapat ditinjau dari 2 hal yaitu efisiensi waktu (seberapa cepat algoritma dieksekusi) dan efisiensi memori (berapa banyak memori yang dibutuhkan untuk menjalankan algoritma). Meskipun algoritma memberikan keluaran yang benar (paling mendekati), tetapi jika kita harus menunggu berjam-jam untuk mendapatkan keluarannya, algoritma tersebut biasanya tidak akan dipakai, setiap orang menginginkan keluaran yang cepat. Begitu juga dengan memori, semakin besar memori yang terpakai maka semakin buruklah algoritma tersebut. Dalam kenyataannya, setiap orang bisa membuat algoritma yang berbeda untuk menyelesaikan suatu permasalahan, walaupun terjadi perbedaan dalam menyusun algoritma, tentunya kita mengharapkan keluaran yang sama. Jika terjadi demikian, carilah algoritma yang paling efisien dan cepat.

>>> Faktor-faktor yang mempengaruhinya adalah :
- Banyak langkah
- Tipe data kecepatan
- Operator-operator
- Alokasi memori  space memori, berkaitan dengan :
• struktur data dinamis
• procedure/function call
• recursif

>>> Tipe data yang digunakan adalah :
- integer
- real
Dua nilai yang sama dengan operator yang sama tetapi dengan variabel yang berbeda, maka terdapat perbedaan kecepatan / proses penyelesaiannya.
















http://id.wikipedia.org/wiki/Algoritma
http://esha.students-blog.undip.ac.id/2010/09/20/matematika-diskrit-kompleksitas-algoritma/
http://wartawarga.gunadarma.ac.id/2011/04/efisiensi-algoritma/