Algorithmic Efficiency

1.      Algoritma.

            Algoritma secara umum atau secara luas adalah tahapan-tahapan yang logis untuk mencapai hasil. Jadi Algoritma tidak selalu berhubungan dengan Ilmu Komputer. Misalkan cara membuat cake. Pertama kita harus mempersiapkan adonan cake. Kemudian apabila adonan tersebut telah jadi, panaskan oven. Kemudian taruh adonan cake tersebut kedalam Loyang yang telah dioleskan mentega dan ditaburi sedikit tepung. Apabila adonan tersebut telah dimasukkan kedalam Loyang,masukkan Loyang yang berisi adonan cake tersebut kedalam oven yang telah di tentukan suhunya tadi. Tunggulah kira-kira setengah jam. Maka adonan cake tersebut akan menjadi kue cake.

            Di sini bukan membahas tentang kue cake, tapi  hanya memberi gambaran logis tentang pengertian Algoritma yang sebenarnya. Yang dapat kita ambil dari contoh di atas adalah untuk menghasilkan sesuatu,maka diperlukan proses. Proses tersebut terdiri dari tahapan-tahapan yang logis. Jadi menurut pemikiran ,secara umum Inti dari algoritma adalah tahapan-tahapan logis yang harus dipenuhi untuk mencapai suatu hasil.

            Sekarang akan membahas Algoritma menurut pengertian ilmu Komputer. Algoritma dalam ilmu Komputer adalah urut-urutan yang logis dan tepat untuk memecahkan permasalahan yang menggunakan Komputer dengan bahasa pemrograman yang telah ditentukan seperti bahasa pascal, Visual Basic, C, atau yang lainnya. Untuk membuat sebuah program, seseorang harus memiliki daya pikir yang bagus. Dan untuk menghasilkan sebuah program yang berbeda dengan yang lainnya, maka orang tersebut harus memiliki kreativitas.

Pembuatan algoritma harus selalu dikaitkan dengan :
a. Kebenaran algoritma, yakni bila program selesai maka hasilnya juga benar.
b. Kompleksitas, lama dan jumlah waktu proses dan penggunaan memori.

            Ciri - ciri algoritma
1. Tepat sasaran.
2. Fleksibel dan portable.
3. Bersih dari kesalahan system ataupun logika.
4. Murah dan efisien.
5. Cepat waktu. 
6. Didokumentasikan.

            Sejarah algoritma :

            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.

2.      Berbagai jenis algoritma.

            Jenis-jenis Algoritma terdapat beragam klasifikasi algoritma dan setiap klasifikasi 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.

A.    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.

B.     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.

C.    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.

Adapun jenis-jenis algoritma yang lain adalah :

1.      Pseudo Code (Kode Semu).

              Pseudo Code (kode semu) merupakan metode yang cukup efisien untuk  menggambarkan suatu algoritma . Pseudo Code dituliskan dengan menggunakan bahasa yang mudah dipahami (boleh menggunakan bahasa Indonesia) agar alur logika yang digambarkan dapat dimengeti oleh orang awam sekalipun. Flowchart  Pseudo Code (kode semu) disusun dengan tujuan untuk menggambarkan  tahap-tahap penyelesaian suatu masalah  dengan kata-kata (teks). Metode ini  mempunyai kelemahan, dimana penyusunan algoritma dengan kode semu sangat  dipengaruhi oleh tata bahasa pembuatnya, sehingga kadang-kdang sulit dipahami oleh orang lain. Oleh karena itu kemudian dikembangkan suatu metode lain  yang dapat menggambarkan suatu algoritma program secara lebih mudah dan sederhana yaitu dengan menggunakan flowchart (diagram alir).

2.      Sistem Flowchart.

            Sistem flowchart merupakan diagram alir yang menggambarkan suatu sistem  peralatan komputer yang digunakan dalam proses pengolahan data serta  hubungan antar peralatan tersebut. Sistem flow chart tidak digunakan untuk  menggambarkan urutan langkah untuk memecahkan masalah , tetapi hanya  untuk menggambarkan prosedur dalam sistem yang dibentuk.

3.      Kompleksitas 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.

            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.

Contoh 1. Menghitung rerata

a1 a2 a3 … an

Larik bilangan bulat

procedure HitungRerata(input a1, a2, …, an : integer, output r : real) { Menghitung nilai rata-rata dari sekumpulan elemen larik integer a1, a2, …, an. Nilai rata-rata akan disimpan di dalam peubah r. Masukan: a1, a2, …, an Keluaran: r (nilai rata-rata) } Deklarasi k : integer jumlah : real Algoritma jumlah 0 k 1 while k n do jumlah jumlah + ak k k+1 endwhile { k > n } r jumlah/n { nilai rata-rata }

1. Operasi pengisian nilai (jumlah 0, k 1, jumlah jumlah+ak, k k+1, dan r jumlah/n). Jumlah seluruh operasi pengisian nilai adalah: t1 = 1 + 1 + n + n + 1 = 3 + 2n
2. Operasi penjumlahan (jumlah+ak, dan k+1). Jumlah seluruh operasi penjumlahan adalah:  t2 = n + n = 2n
3. Operasi pembagian (jumlah/n). Jumlah seluruh operasi pembagian adalah t3 = 1

Total kebutuhan waktu algoritma HitungRerata:

t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c detik

            Model perhitungan kebutuhan waktu seperti di atas kurang berguna, karena dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu. Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya.

            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.

            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.

4.      Algoritma yang efisien.

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.

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

Ø Operator

            Urutan penggunaan operator/penempatan operator bisa mempengaruhi efisiensi. Misalkan dalam sebuah perhitungan algoritma terdapat operator perkalian (*) dan penjumlahan (+), maka operator yang paling mempengaruhi efisiensi adalah perkalian (*) karena proses perkalian (*) lebih lama daripada proses penjumlahan (+)
• Tetapi dalam perkembangan teknologi, perbedaan penggunaan operator maupun tipe data dasar tidak terlalu signifikan.
• Yang perlu diperhatikan adalah banyaknya operasi aritmatika dan logika yang dilakukan.

Operator aritmatika : +, -, *, /, ^.
            Operator logika : AND, OR, NOT masing-masing 1 kali operation. Operator adalah jika hasil perhitungannya termasuk dalam himpunan itu sendiri.
2 <  bukan operator tapi konstanta logika karena tidak menghasilkan nilai yang sejenisà5
 HàOperator : H x H

x = 2<5
x = True Tidak ada operation ( 0 operation)
y = 5
y = 5+0 à 1 operation
y = 2+3*5 à 2 operation
y = 3*5+2 à 2 operation

Contoh Program :

Perhatikan potongan program beikut ini yang menghitung jumlah n buah suatu bilangan riil

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.
1. Bagian a, eksukusi satu kali
2. Bagian b, merupakan bagian loop, langkah itu akan diproses berdasarkan kenaikan harga i dari i = 1 hingga i = n . Jadi, statement sum=sum+v[i] akan diproses sebanyak n kali sesuai dengan kenaikan harga i
3. Bagian c, akan di proses sekali

                Jadi, dapat disimpulkan karena bagian b merupakan bagian yang paling sering diproses, maka bagian b merupakan operasi aktif. Sedangkan bagian a dan c dapat diabaikan karena bagian -bagian tersebut tidak diproses sesering bagian b.
Banyak kali bagian b diproses sama banyaknya dengan data yang dimasukan (=n). Dengan demikian, program penjumlahan n buah bilangan rill memiliki order sebanding dengan n, dengan kata lain program memiliki O(n).