Greatest Common Divisor Algorithm

GCD (Pembagi Umum Terbesar)

GCD, atau Greatest Common Divisor (Pembagi Umum Terbesar), adalah bilangan bulat positif terbesar yang dapat membagi dua atau lebih bilangan bulat tanpa meninggalkan sisa. Dalam kata lain, GCD dari dua bilangan adalah bilangan terbesar yang dapat membagi kedua bilangan tersebut.

Contoh

Mari kita lihat contoh untuk menghitung GCD dari dua bilangan, misalnya 48 dan 18.

Faktor dari 48:

• 1, 2, 3, 4, 6, 8, 12, 16, 24, 48

Faktor dari 18:

• 1, 2, 3, 6, 9, 18

Faktor Umum:

• 1, 2, 3, 6

Dari faktor-faktor di atas, GCD dari 48 dan 18 adalah 6 karena 6 adalah bilangan terbesar yang dapat membagi kedua bilangan tersebut.

Metode untuk Menghitung GCD

Salah satu metode yang umum digunakan untuk menghitung GCD adalah Algoritma Euclid. Algoritma ini bekerja dengan cara berikut:

1. Ambil dua bilangan, misalnya a dan b.
2. Jika b adalah 0, maka GCD adalah a.
3. Jika tidak, lakukan langkah berikut: GCD(a, b) = GCD(b, a mod b).

Contoh menggunakan Algoritma Euclid:

Mari kita hitung GCD dari 48 dan 18 menggunakan algoritma ini:

GCD(48, 18)
48 mod 18 = 12
GCD(18, 12)
18 mod 12 = 6
GCD(12, 6)
12 mod 6 = 0
GCD(6, 0) = 6

Jadi, GCD dari 48 dan 18 adalah 6.

Algoritma Euclid untuk menghitung GCD (Greatest Common Divisor) memiliki kompleksitas waktu yang cukup efisien. Berikut adalah penjelasan mengenai kompleksitasnya:

1. Kompleksitas Waktu:

   • Algoritma Euclid melakukan operasi pengurangan (atau modulus) pada dua bilangan $a$ dan $b$ secara berulang hingga salah satu bilangan menjadi nol. Dalam hal ini, kompleksitas waktu algoritma adalah $O(\log(\min(a, b)))$. Hal ini disebabkan karena pada setiap langkah, bilangan yang lebih kecil secara bertahap mengecil hingga menjadi nol.

2. Kompleksitas Ruang:

   • Algoritma ini memiliki kompleksitas ruang $O(1)$ jika menggunakan pendekatan iteratif, karena hanya memerlukan sejumlah kecil variabel tambahan untuk menyimpan nilai sementara.

Secara keseluruhan, algoritma Euclid sangat efisien dan sering digunakan dalam berbagai aplikasi yang memerlukan perhitungan GCD.

Mari kita hitung GCD dari $a = 48$ dan $b = 18$ menggunakan algoritma Euclid, dan kemudian kita akan menilai kompleksitasnya.

1. Langkah-langkah Algoritma Euclid:
   • $GCD(48, 18)$
     
     • $48 \mod 18 = 12$ (48 dibagi 18 sisanya 12)
   • $GCD(18,12)$
     • $18 \mod 12 = 6$ (18 dibagi 12 sisanya 6)
   • $GCD(12,6)$
     • $12 \mod 6 = 0$ (12 dibagi 6 sisanya 0)

Setelah langkah terakhir, kita menemukan bahwa $GCD(48, 18) = 6$.

2. Menghitung Kompleksitas:

   • Kita memiliki dua angka, $a = 48$ dan $b = 18$.
   • Nilai terkecil di sini adalah $b = 18$.
   • Untuk menentukan kompleksitas waktu, kita lihat bahwa algoritma melakukan 3 langkah sebelum mencapai hasil akhir:
     1. Menghitung $GCD(48,18)$
     2. Menghitung $GCD(18, 12)$
        
     3. Menghitung $GCD(12, 6)$
        
     4. Mencapai $GCD(6, 0)$ untuk hasil akhir.

3. Evaluasi Kompleksitas:

   • Kompleksitas waktu algoritma adalah $O(\log(\min(48, 18))) = O(\log(18))$.
   • Jika kita menghitung logaritma basis 2:
     • $\log_2(18) \approx 4.17$ (ini menunjukkan bahwa algoritma memiliki sekitar 4 langkah dalam pengurangan nilai untuk menyelesaikan perhitungan GCD).
   • Secara praktis, algoritma hanya melakukan beberapa operasi sebelum mencapai hasil, sehingga kompleksitasnya dapat dianggap efisien.

Jadi, dalam kasus ini, meskipun kita melakukan 3 langkah secara eksplisit, kompleksitas algoritma secara teori tetap $O(\log(18))$, yang mencerminkan efisiensi algoritma ketika beroperasi pada angka yang lebih besar.

1. Metode Iterasi

Kelebihan:

• Memori yang Efisien: Algoritma iteratif tidak menggunakan tumpukan memori tambahan untuk panggilan fungsi, sehingga lebih efisien dalam penggunaan memori.
• Lebih Stabil: Tidak rentan terhadap stack overflow yang dapat terjadi pada rekursi, terutama untuk nilai-nilai yang sangat besar.

Contoh Kode:

def euclidean_gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

2. Metode Rekursi

Kelebihan:

• Keterbacaan: Kode rekursif sering kali lebih mudah dibaca dan ditulis, karena langsung mengikuti definisi matematis GCD.
• Elegan: Menggunakan pendekatan matematis yang lebih langsung.

Contoh Kode:

def euclidean_gcd_recursive(a, b):
    if b == 0:
        return a
    return euclidean_gcd_recursive(b, a % b)

Perbandingan Efisiensi

Aspek	Iterasi	Rekursi
Penggunaan Memori	Lebih rendah, tidak menggunakan stack tambahan	Memerlukan lebih banyak memori untuk tumpukan
Kecepatan	Biasanya lebih cepat karena tidak ada overhead panggilan fungsi	Lebih lambat karena overhead panggilan fungsi
Kemudahan Pemahaman	Bisa jadi lebih rumit untuk dibaca pada beberapa algoritma	Lebih mudah dibaca untuk definisi yang matematis
Risiko	Tidak ada risiko stack overflow	Risiko stack overflow pada input besar

Kesimpulan

Untuk GCD, metode iterasi sering kali lebih efisien dalam hal penggunaan memori dan stabilitas, terutama untuk bilangan besar. Metode rekursi lebih cocok ketika keterbacaan dan elegan lebih diutamakan, tetapi perlu diperhatikan risiko stack overflow.

Secara keseluruhan, untuk algoritma GCD, lebih disarankan menggunakan metode iterasi, terutama jika ada kemungkinan input yang besar. Jika Anda bekerja dengan input yang lebih kecil dan fokus pada keterbacaan, metode rekursi juga dapat dipertimbangkan.