Menyangkilkan Algoritma

“Menyangkilkan” berasal dari kata “sangkil”, yang salah satu artinya adalah “berdaya guna/efisien” (artinya ada di situ).

Baru denger kan? Hehe. Sama. Penulis juga.

Mengapa perlu algoritma yang sangkil?

  • Algoritma yang sangkil akan membuat program yang kita buat menjadi bekerja lebih cepat, karena kembali lagi ke fungsi komputer yang sebenarnya, yaitu mempercepat pekerjaan yang lambat dikerjakan oleh manusia secara langsung.
  • Selain itu, algoritma yang sangkil tentu akan memperingan kerja mesin, terlebih bagi mesin yang kemampuannya hanya bisa melakukan sedikit operasi per satuan waktu.

Tingkat kesangkilan suatu algoritma biasanya menggunakan satuan kompleksitas algoritma dengan notasi Big-O.
Salah satu cara untuk menyangkilkan algoritma yang kita buat adalah menganalisis kembali algoritma kita tadi. Di bawah ini penulis memberi satu contoh permasalahan dan beberapa algoritma untuk menyelesaikannya.


Permasalahan

Diberikan bilangan bulat positif A dan B. Tentukan digit terakhir dari AB.

Seperti yang kita tahu, untuk mencari digit terakhir dari suatu bilangan N, cukup dengan menghitung N di-modulo dengan 10. FYI, soal ini pernah digunakan untuk pemanasan C-Compiler UGM 2017 bidang Competitive Programming, tapi waktu itu nilai A = 2 saja. Baik, langsung saja solusinya.

Cara Naif

Kita menghitung AB secara linear terlebih dahulu, kemudian hasilnya kita modulo dengan 10.

Contoh, jika kita ingin menghitung 29, kita akan menghitung 2*2 dulu. Lalu hasilnya kita kalikan dengan 2 lagi, dan begitu seterusnya. Implementasinya ada di program di bawah ini.

Terlihat mudah? Kenyataannya, pada beberapa bahasa pemrograman (seperti C atau C++), nilai AB akan menyebabkan overflow. Selain itu untuk B sangat besar, algoritma ini bekerja sangat lama.

Algoritma ini memiliki kompleksitas sebesar O(B). Jika suatu mesin hanya bisa menjalankan 100.000.000 (seratus juta) operasi setiap detiknya, untuk menghitung digit terakhir dari A720.000.000.000 (pangkat tujuh ratus dua puluh milyar) secara kasar setidaknya mesin memerlukan waktu 2 jam untuk menyelesaikannya.

Kelebihan :
Sangat intuitif, terutama bagi pemula
Kekurangan :
Menyebabkan overflow pada beberapa bahasa pemrograman, lambat
Kompleksitas algoritma :
O(B)
Perkiraan kasar :
Untuk menghitung A720.000.000.000 perlu waktu 2 jam, dengan kemampuan mesin seratus juta operasi per detik.

Analisis Level 1

Secara matematika, berdasarkan sifat modulo, jika kita menghitung (X * Y) mod M, maka hasilnya sama saja dengan

[(X mod M) * (Y mod M)] mod M

Dari sini kita bisa sedikit mengubah algoritma kita, dari yang tadinya menghitung AB dulu kemudian di-modulo, sekarang sambil menghitung hasil perpangkatan, kita juga sambil menghitung modulonya. Implementasinya :

Namun tetap saja kompleksitas dari algoritma ini tidak berubah; masih sebesar O(B).

Kelebihan :
Menghindari overflow
Kekurangan :
Tidak seintuitif cara sebelumnya
Kompleksitas algoritma :
O(B)
Perkiraan kasar :
Untuk menghitung A720.000.000.000 perlu waktu 2 jam, dengan kemampuan mesin seratus juta operasi per detik.

Analisis Level 2

Jika kita perhatikan, jika B genap, menghitung AB sebenarnya sama saja dengan menghitung

AB/2 * AB/2

Jika B ganjil, sama saja dengan menghitung

A * A(B-1)/2 * A(B-1)/2

Contoh, jika kita ingin menghitung 29, maka hasilnya sama saja dengan menghitung 2*(24)*(24). Kemudian untuk menghitung 24 , kita bisa mengulangi langkah membagi dua seperti tadi lagi.

Lalu dengan menggunakan sifat modulo di atas, kita bisa menghitung modulo sambil menghitung hasil perpangkatan, untuk menghindari overflow. Berikut implementasinya secara rekursif.

Metode ini selanjutnya dikenal dengan nama Divide and Conquer; membagi-bagi permasalahan ke permasalahan yang lebih kecil terlebih dulu.

Kelebihan :
Menghindari overflow, bekerja jauh lebih cepat dibandingkan algoritma sebelumnya. Perhatikan perkiraan kasar di bawah.
Kekurangan :
Lebih tidak intuitif dibandingkan algoritma sebelumnya
Kompleksitas algoritma :
O(log B)
Perkiraan kasar :
Untuk menghitung A720.000.000.000 perlu waktu 0.000000108 detik, dengan kemampuan mesin seratus juta operasi per detik. Cukup cepat? Ada yang lebih cepat lagi!

Analisis Level 3

Jika kita perhatikan lagi, ternyata digit terakhir dari AB berpola. Pola dan periode berulangnya tergantung nilai A. Contoh, untuk A = 2, perhatikan pola di bawah ini.

21 mod 10 = 2
22 mod 10 = 4
23 mod 10 = 8
24 mod 10 = 6
25 mod 10 = 2

Boom! Jika kita lanjutkan lagi dengan 26, tentu digit terakhirnya akan menjadi 4, dan akan kembali mengulangi pola yang di atasnya. Itu untuk contoh A = 2 yang periodenya setiap B bertambah 4. Untuk A = 4 atau 9, polanya berulang setiap B bertambah 2. Untuk A = 10, 1, 15, atau 26, polanya malah berulang setiap B bertambah 1 hehe. Implementasinya sebagai berikut :

Kelebihan :
Tidak mungkin overflow, jauh lebih cepat bahkan dari algoritma sebelumnya
Kekurangan :
Paling tidak intuitif. Perlu observasi mendalam bagi pemula.
Kompleksitas algortma :
O(1)
Perkiraan kasar :
Untuk menghitung A720.000.000.000 perlu waktu 0.00000000001 detik, dengan kemampuan mesin seratus juta operasi per detik.


TL; DR? Too long didn’t read?
Maafkan, penulis memang belum terlatih untuk menulis secara sederhana hehe. Intinya, sering-sering latihan aja biar terbiasa menyangkilkan algoritma. Sekian. Semoga pos ini bermanfaat buat pembaca sekalian 🙂

Tinggalkan Balasan