ALGORITMA DAN KOMPLEKSITAS (Decrease and conquer)

DECREASE AND CONQUER

Pembahasan

 Decrease and conquer: metodedesain algoritma dengan mereduksi persoalan menjadi beberapa sub-persoalan yang lebih kecil, tetapi selanjutnya hanyamemproses satu sub-persoalan saja.

 Berbeda dengan divide and conquer  yang memproses semua sub-persoalan dan menggabung semua solusi setiap sub-persoalan.
 Decrease and conquer terdiri dari dua tahapan:
 1. Decrease: mereduksi persoalan menjadi beberapa persoalan yang lebih kecil (biasanya dua subpersoalan).
2. Conquer: memproses satu sub-persoalan secara rekursif.
 Tidak ada tahap combine dalam decrease and conquer

Tiga variandecrease and conquer: 
1. Decrease by a constant: ukuraninstans persoalan direduksi sebesar konstanta yang samasetiap iterasi algoritma. Biasanya konstanta = 1.
2. Decrease by a constant factor: ukuraninstans persoalan direduksi sebesar faktorkonstanta yang samasetiap iterasi algoritma. Biasanya faktorkonstanta = 2.
3. Decrease by a variable size: ukuraninstans persoalan direduksi bervariasi padasetiap iterasi algoritma.

Decrease by a constant
 Contoh 1: Persoalan perpangkatan an
Dengan metode decrease and conquer:

Kompleksitas waktu (berdasarkanjumlahoperasi kali):

Bila diselesaikan:

T(n) = T(n –1) + 1 = …. = O(n)


sama seperti algoritma brute-force.

function exp(a : real; n: integer) real 

Deklarasi k: integer

Algoritma: ifn= 0 

then return1 

else returnexp(a, n– 1) * a 

endif

CONTOH : 

Misalkan tabel aberisi elemen-elemen berikut: 4 12 3 9 1 21 5 2 Langkah-langkah pengurutan dengan Selection Sort: