Apa itu algoritma

Metode mencari faktor persekutuan terbesar dalam Buku VII Elements karya Euclid, yang ditulis sekitar 2300 tahun lalu, masih berjalan di komputer sampai sekarang.

Metode yang selalu berhasil

Misalkan kamu perlu mencari bilangan terbesar yang habis membagi 1071 dan 462. Kamu bisa mencoba setiap bilangan dari 462 turun sampai 1 dan berhenti di bilangan pertama yang habis membagi keduanya. Cara itu berhasil, tetapi bisa butuh ratusan percobaan. Ada cara yang lebih singkat. Bagi 1071 dengan 462 dan simpan sisanya, 147. Sekarang bagi 462 dengan 147 dan simpan sisanya, 21. Bagi 147 dengan 21: sisanya 0, jadi jawabannya 21. Tiga pembagian, bukan beberapa ratus.

Cara singkat itu adalah algoritma: daftar langkah tepat yang jumlahnya terbatas, yang menerima suatu masukan dan menghasilkan keluaran yang benar. Yang ini adalah algoritma Euclid untuk faktor persekutuan terbesar, dan algoritma ini muncul dalam Buku VII Elements, yang ditulis sekitar tahun 300 SM. Euclid menjelaskannya dengan pengurangan panjang berulang kali, bukan pembagian, tetapi idenya sama, dan versi dengan sisa bagi itulah yang dipakai program sekarang.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // sisa bagi
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Apa yang membuat daftar langkah menjadi algoritma

Buku teks seperti karya Cormen, Leiserson, Rivest, dan Stein menggambarkan algoritma sebagai prosedur yang terdefinisi dengan baik untuk mengubah masukan menjadi keluaran. Ada tiga hal yang terkandung dalam gambaran itu, dan masing-masing penting saat kamu menulis kode.

• Tepat. Setiap langkah hanya punya satu arti. "Bagi a dengan b dan simpan sisanya" itu tepat; "buat bilangannya jadi lebih kecil entah bagaimana" tidak.
• Terbatas. Algoritma harus berhenti. Dalam algoritma Euclid, sisanya selalu lebih kecil daripada bilangan pembaginya, jadi sisa itu mengecil setiap putaran dan pasti mencapai 0.
• Benar. Untuk setiap masukan yang diizinkan, keluarannya adalah jawaban yang benar, bukan hanya untuk contoh yang kamu coba.

Resep masakan sering dijadikan contoh sehari-hari, dan itu contoh yang wajar: bahan adalah masukan, hidangan adalah keluaran, dan langkah-langkahnya berurutan. Bedanya ada pada seberapa banyak yang diisi sendiri oleh pembacanya. Juru masak memutuskan sendiri arti "sejumput". Komputer tidak memutuskan apa pun, karena itulah algoritma untuk komputer ditulis dengan setiap langkah dijabarkan lengkap.

Masalah sama, algoritma berbeda

Satu masalah biasanya punya banyak algoritma yang benar, dan banyaknya pekerjaan yang dilakukan masing-masing bisa sangat berbeda. Untuk faktor persekutuan terbesar dari 1071 dan 462, mencoba setiap bilangan dari 462 ke bawah butuh 442 percobaan sebelum sampai ke 21, sedangkan metode Euclid butuh 3 pembagian. Keduanya benar. Hanya satu yang cepat. Sebagian besar kursus ini membahas pertanyaan kedua itu: setelah sebuah metode benar, berapa langkah yang dibutuhkannya, dan bagaimana jumlah itu bertambah saat masukannya makin besar?

Untuk menjawabnya, ilmuwan komputer menghitung langkah dasar (satu perbandingan, satu pertukaran, satu pembagian), bukan detik. Detik bergantung pada mesinnya. Jumlah langkah hanya bergantung pada algoritma dan masukannya, jadi kamu bisa membandingkan dua metode dengan adil. Lab di bawah menghitung perbandingan untukmu sambil mengurutkan sederet batang. Coba urutan awal yang sama dengan dua metode berbeda dan perhatikan penghitungnya.

Masukan, keluaran, dan langkah di antaranya

Sebelum menulis algoritma, tuliskan dengan tepat apa yang masuk dan apa yang harus keluar. Untuk faktor persekutuan terbesar: masukannya dua bilangan bulat positif, dan keluarannya satu bilangan bulat yang habis membagi keduanya, tanpa ada bilangan lebih besar yang juga bisa. Gambaran itu memberi tahu cara menguji hasilnya, dan sering memberi petunjuk tentang langkah-langkahnya. Gambaran itu juga memperlihatkan kasus tepi: bagaimana kalau salah satu bilangan 0? (Perulangan di atas mengembalikan bilangan yang lain, dan itu jawaban yang benar.) Bagaimana kalau kedua bilangan sama? Memikirkan kasus tepi sebelum menjalankan kode bisa menangkap banyak kesalahan.