📉

Desain dan Analisis Algoritma

Paradigma
Decrease and Conquer

Kurangi · Selesaikan · Perluas Solusi

Variasi

3

by 1 · by factor · variable

Contoh

6+

Insertion, Binary, GCD, dll.

Implementasi

2

Top-down & Bottom-up

Definisi & Intuisi

Apa itu Decrease and Conquer?

Decrease and Conquer adalah teknik desain algoritma yang menyelesaikan masalah dengan cara mengurangi ukuran instance menjadi lebih kecil, menyelesaikan instance kecil tersebut, lalu memperluas solusinya ke masalah semula.

Berbeda dengan Divide and Conquer yang biasanya menghasilkan beberapa submasalah yang semuanya harus diselesaikan, Decrease and Conquer hanya menghasilkan satu submasalah yang lebih kecil di setiap langkah.

Alias: incremental / inductive approach.

Skema Umum

// Skema Decrease and Conquer solve(problem of size n): // 1. Decrease bentuk submasalah S' berukuran lebih kecil (< n) // 2. Conquer selesaikan S' (rekursif / iteratif) // 3. Extend perluas solusi S' → solusi S

Perbandingan Paradigma

Decrease vs Divide and Conquer

Beberapa penulis menyarankan: istilah Divide and Conquer dipakai hanya ketika setiap masalah dipecah menjadi ≥ 2 submasalah, sedangkan kasus satu submasalah lebih tepat disebut Decrease and Conquer.

Aspek	Divide and Conquer	Decrease and Conquer
# Submasalah	Biasanya ≥ 2 (Merge Sort: 2, Quick Sort: 2)	Selalu 1 (misalnya Binary Search)
Contoh utama	Merge Sort, Quick Sort, Strassen	Insertion Sort, Binary Search, Euclid GCD
Rekurens umum	T(n) = aT(n/b) + f(n), a ≥ 2	T(n) = T(g(n)) + f(n), g(n) < n
Analogi	Memecah pekerjaan ke beberapa tim	Mengerjakan langkah demi langkah, mengurangi beban

Tiga Variasi

Variasi Decrease and Conquer

1. Decrease by a Constant

Ukuran masalah dikurangi dengan konstanta tetap (biasanya 1) di setiap langkah.

• Insertion Sort
• DFS, BFS (graf)
• Topological Sort
• Generating permutations, subsets

2. Decrease by a Constant Factor

Ukuran masalah dikurangi dengan faktor konstan (sering 2) di setiap langkah.

• Binary Search
• Exponentiation by squaring
• Russian Peasant Multiplication
• Fake-coin problem

3. Variable-Size Decrease

Pengurangan ukuran tidak tetap; bergantung pada data.

• Euclid’s GCD
• Selection / partition-based
• Beberapa algoritma BST
• Nim-like games

Contoh 1 — Decrease by 1

Insertion Sort sebagai Decrease and Conquer

Ide: untuk mengurutkan A[0..n−1], asumsikan A[0..n−2] sudah terurut. Tugas kita hanya menyisipkan A[n−1] ke posisi yang tepat.

Ini adalah contoh klasik decrease-by-one: masalah ukuran n direduksi menjadi masalah ukuran n−1 yang sudah diselesaikan.

Contoh langkah

6 | 4 1 8 5
4 6 | 1 8 5
1 4 6 | 8 5
1 4 6 8 | 5
1 4 5 6 8 ✓

// Pseudocode Insertion Sort procedure InsertionSort(A[0..n-1]) for i = 1 to n-1 do v ← A[i] j ← i - 1 while j ≥ 0 and A[j] > v do A[j+1] ← A[j] j ← j - 1 A[j+1] ← v // Ukuran masalah: panjang prefix yang belum diproses // Setiap iterasi: n → n-1 elemen yang belum tersortir

Analisis Insertion Sort

Kompleksitas Decrease-by-One

Waktu

• Worst-case: array terbalik → ~ n(n−1)/2 pergeseran → Θ(n²).
• Best-case: sudah terurut → hanya 1 perbandingan per iterasi → Θ(n).
• Average-case: ≈ n²/4 perbandingan → Θ(n²).

Ruang & sifat

• In-place: butuh O(1) ekstra memori.
• Stabil: elemen dengan key sama tidak saling melompati.
• Sangat efisien untuk array kecil / hampir terurut.

Mengapa ini Decrease and Conquer?

• Pada iterasi i, kita menganggap subarray A[0..i−1] sudah tersortir (solusi masalah ukuran i).
• Kita mengurangi masalah dengan menghilangkan elemen terakhir A[i], menyelesaikan masalah yang lebih kecil, lalu memasukkan kembali A[i] pada posisi benar.
• Hubungan solusi n dan n−1 menjadi sangat eksplisit.

Contoh 2 — Decrease by Factor

Binary Search sebagai Decrease-by-Half

Binary Search mencari elemen dalam array terurut dengan membandingkan ke elemen tengah dan menghapus setengah ruang pencarian di setiap langkah.

• Ukuran masalah n → n/2 → n/4 → ... → 1.
• Rekurens worst-case: C(n) = C(⌊n/2⌋) + 1.
• Solusi: C(n) = Θ(log₂ n).

Intuisi

Untuk n = 1.000.000, worst-case hanya sekitar 20 langkah pencarian.

// Pseudocode Binary Search (iteratif) function BinarySearch(A[0..n-1], key): l ← 0; r ← n-1 while l ≤ r: m ← ⌊(l+r)/2⌋ if A[m] == key: return m elif key < A[m]: r ← m-1 else: l ← m+1 return -1 // Decrease-by-factor: ukuran interval selalu dibagi dua

Contoh 3 — Variable Decrease

Euclid’s Algorithm untuk GCD

Euclid’s algorithm menghitung gcd(m, n) dengan identitas gcd(m, n) = gcd(n, m mod n), selama n ≠ 0.

• Setiap langkah: masalah (m, n) → (n, m mod n).
• Ukuran berkurang tidak tetap, tapi dapat dibuktikan minimal berkurang cukup cepat.
• Kompleksitas: Θ(log n).

Contoh

gcd(80, 44) = gcd(44, 36)
= gcd(36, 12)
= gcd(12, 0) = 12

// Euclid's Algorithm (iteratif) function GCD(m, n): while n ≠ 0: r ← m mod n m ← n n ← r return m // Variable-size decrease pada argumen kedua

Rangkuman Contoh

Tabel Ringkas Algoritma Decrease and Conquer

Algoritma	Jenis Decrease	Rekurens / Analisis	Waktu	Catatan
Insertion Sort	By 1	Perbandingan ~ n(n−1)/2 (worst)	Θ(n²)	In-place, stabil, baik untuk n kecil
Binary Search	By 1/2	C(n) = C(n/2)+1	Θ(log n)	Butuh array terurut
Euclid GCD	Variable	Ukuran turun ≥ 1/2 tiap 2 langkah	Θ(log n)	Sangat tua & sangat efisien
Topological Sort	By 1 (hapus simpul)	DFS / source removal	Θ(V+E)	Dag, prerequisite scheduling

Kesimpulan

Mengapa Decrease and Conquer Penting?

Paradigma ini memberikan cara berpikir incremental: selesaikan versi kecil dari masalah, lalu bangun solusi penuh darinya. Banyak algoritma praktis—dari sorting sederhana hingga algoritma graf—secara alami mengikuti pola ini.

🧩

Konseptual

Mendekatkan cara berpikir algoritmik dengan pembuktian induktif.

⚙️