Decrease and Conquer

Decrease and conquer adalah metode desain algoritma dengan mereduksi persoalan menjadi beberapa sub-persoalan yang lebih kecil, tetapi selanjutnya hanya memproses satu sub-persoalan saja. Metode ini memiliki dua tahapan, antara lain:

1. Decrease, yaitu mereduksi persoalan menjadi beberapa persoalan yang lebih kecil (biasanya dua sub-persoalan).
2. Conquer, yaitu memproses satu sub-persoalan secara rekursif.

Terdapat tiga varian pengurangan pada metode decrease and conquer, antara lain decrease by a constant, decrease by a constant factor, dan decrease by a variable size.

Decrease by a constant 

Pada varian ini, ukuran instans persoalan direduksi sebesar konstanta yang sama setiap iterasi algoritma. Umumnya, konstanta yang digunakan bernilai sama dengan 1. Salah satu contoh dari varian ini adalah penyelesaian perpangkatan aⁿ. Penyelesaiannya dapat dilihat di bawah ini.

Dengan metode decrease and conquer, maka:

 Kompleksitas waktu (berdasarkan jumlah kali) adalah sebagai berikut:

Decrease by a constant factor

Pada varian ini, ukuran instans persoalan direduksi sebesar faktor konstanta yang sama setiap iterasi algoritma. Salah satu contoh menggunakan varian ini adalah binary search, yang bila diilustrasikan prosesnya menjadi seperti berikut.

Decrease by a variable size 

Pada varian ini, ukuran instans persoalan direduksi bervariasi pada setiap iterasi algoritma. Contoh algoritma yang menggunakan varian pengurangan decrease by a variable size adalah algoritma Euclid. Penyelesaian algoritma Euclid adalah sebagai berikut.

gcd(m,n) = gcd(n, m mod n)

Contoh:

gcd(80,12) --> 80:12 = 6 sisa 8

gcd (12, 8) --> 12:8 = 1 sisa 4

gcd (8,4) --> 8:4 = 2 sisa 0

Jadi, gcd (80,12) = gcd (12, 8) = gcd (8, 4) = gcd (4, 0) = 4.