⚔️
Desain & Analisis Algoritma

Algoritma
Divide and Conquer

Pecah · Taklukkan · Gabungkan

O(n log n)
Merge Sort
O(log n)
Binary Search
3 Langkah
Paradigma Inti
Navigasi Materi

Daftar Isi

01
Pendahuluan & Definisi
Apa itu Divide and Conquer?
02
Tiga Tahap Utama
Divide · Conquer · Combine
03
Merge Sort
Algoritma & Kompleksitas O(n log n)
04
Quick Sort
Pivot & Partisi Array
05
Binary Search
Pencarian O(log n)
06
Master Theorem
Analisis Rekurens T(n)
07
Perbandingan & Kelebihan
vs Brute Force & DP
08
Aplikasi & Kesimpulan
Dunia Nyata & Ringkasan
Definisi

Apa itu Divide and Conquer?

Paradigma desain algoritma yang menyelesaikan masalah besar dengan cara memecahnya secara rekursif menjadi submasalah yang lebih kecil, lalu menggabungkan solusinya.

🏛️

Asal Usul Istilah

Berasal dari strategi militer Romawi "divide ut imperes" — memecah kekuatan musuh agar mudah dikalahkan. Diterapkan dalam ilmu komputer sejak era 1945 oleh John von Neumann (Merge Sort).

🧩

Analogi Puzzle

Bayangkan puzzle 1000 keping — bagi menjadi kelompok kecil, selesaikan tiap kelompok secara mandiri, lalu gabungkan hasilnya menjadi gambar utuh.

Ciri Khas Algoritma D&C

  • ▸ Bersifat rekursif — memanggil dirinya sendiri dengan input lebih kecil
  • ▸ Submasalah bersifat independen — tidak saling bergantung (berbeda dari DP)
  • ▸ Memiliki base case yang menghentikan rekursi
  • ▸ Efisien untuk input besar, sering mencapai O(n log n)
  • ▸ Dapat diimplementasikan secara paralel di sistem multiprosesor
Paradigma Inti

Tiga Tahap Divide and Conquer

🔪
DIVIDE
(Membagi)

Bagi masalah berukuran n menjadi a submasalah, masing-masing berukuran n/b. Proses pembagian harus menghasilkan submasalah yang serupa dengan masalah asal.

T(n/b) — ukuran setelah dibagi
⚡
CONQUER
(Menaklukkan)

Selesaikan setiap submasalah secara rekursif. Jika submasalah cukup kecil (base case: n ≤ n₀), selesaikan langsung tanpa rekursi lebih lanjut.

Base case: n ≤ n₀ → SOLVE
🔗
COMBINE
(Menggabungkan)

Gabungkan solusi dari semua submasalah menjadi solusi final masalah utama. Tahap ini menentukan total kompleksitas tambahan f(n).

f(n) — biaya penggabungan
Rekurens umum: T(n) = a · T(n/b) + f(n) — dimana a ≥ 1, b > 1
Contoh Kasus 1

Merge Sort — Pengurutan Rekursif

Merge Sort membagi array menjadi dua bagian sama besar secara rekursif hingga ukuran 1, lalu menggabungkan kembali dalam urutan terurut. Ditemukan oleh John von Neumann, 1945.

Visualisasi Array [38, 27, 43, 3]
DIVIDE:[38,27]|[43,3]
→[38] [27]|[43] [3]
MERGE:[27,38]+[3,43]
FINAL:[3, 27, 38, 43] ✓
O(n log n)
Best / Avg / Worst
O(n)
Space Complexity
Stabil
Stable Sort
// Pseudocode Merge Sort function MergeSort(arr, l, r): if l < r: mid = (l + r) // 2 // DIVIDE: bagi dua bagian MergeSort(arr, l, mid) MergeSort(arr, mid+1, r) // COMBINE: gabungkan terurut Merge(arr, l, mid, r) function Merge(arr, l, mid, r): i, j = l, mid+1 temp = [] while i ≤ mid and j ≤ r: if arr[i] ≤ arr[j]: temp.append(arr[i++]) else: temp.append(arr[j++]) // salin sisa elemen salin sisa i atau j ke temp arr[l..r] = temp // Rekurens: T(n) = 2T(n/2) + O(n) // → T(n) = O(n log n)
Contoh Kasus 2

Quick Sort — Pivot & Partisi

// Pseudocode Quick Sort function QuickSort(arr, low, high): if low < high: // DIVIDE: pilih pivot, partisi p = Partition(arr, low, high) // CONQUER: rekursi dua sisi QuickSort(arr, low, p-1) QuickSort(arr, p+1, high) // COMBINE: tidak diperlukan! function Partition(arr, low, high): pivot = arr[high] // pilih pivot i = low - 1 for j = low to high-1: if arr[j] ≤ pivot: i++ swap(arr[i], arr[j]) swap(arr[i+1], arr[high]) return i + 1

Quick Sort menggunakan elemen pivot untuk mempartisi array: elemen lebih kecil di kiri, lebih besar di kanan. Proses ini dilakukan rekursif hingga array terurut.

Contoh Partisi dengan Pivot = 5
Input :[3, 6, 8, 10, 1, 2, 5]
Kiri :[3, 1, 2] ← < 5
Kanan :[6, 8, 10] ← > 5
Hasil :[1,2,3] 5 [6,8,10]
O(n log n)
Best / Average
O(n²)
Worst Case
O(log n)
Space (avg)
Contoh Kasus 3

Binary Search — Pencarian Efisien

Binary Search bekerja pada array terurut. Setiap iterasi, rentang pencarian dipotong menjadi setengahnya, menghasilkan efisiensi O(log n) dibanding O(n) pada pencarian linear.

Cari angka 7 dalam [1,3,5,7,9,11,13]
Langkah 1: [1,3,5,7,9,11,13] mid=7 → KETEMU! ✓
Hanya 1 langkah dari 7 elemen!
Tanpa Binary (linear): 4 perbandingan
Dengan Binary Search: 1 perbandingan
O(log n)
Binary Search
vs
O(n)
Linear Search
→
1000x lebih cepat
untuk n=1.000.000
// Pseudocode Binary Search function BinarySearch(arr, target): low = 0 high = len(arr) - 1 while low ≤ high: mid = (low + high) // 2 // DIVIDE: cek tengah if arr[mid] == target: return mid // FOUND // CONQUER: pilih setengah elif arr[mid] < target: low = mid + 1 // kanan else: high = mid - 1 // kiri return -1 // tidak ditemukan // Rekurens: T(n) = T(n/2) + O(1) // → T(n) = O(log n) // Syarat: array harus TERURUT
Analisis Kompleksitas

Master Theorem

Alat analitis untuk menyelesaikan rekurens bentuk T(n) = aT(n/b) + f(n), dimana a ≥ 1 (jumlah submasalah), b > 1 (faktor pembagi), f(n) (biaya combine).

KASUS 1
Submasalah mendominasi
f(n) = O(nlog_b(a)-ε)
T(n) = Θ(nlog_b(a))
Contoh: T(n) = 8T(n/2) + O(n²) → T(n) = Θ(n³)
KASUS 2
Keduanya seimbang
f(n) = Θ(nlog_b(a) · logkn)
T(n) = Θ(nlog_b(a) logk+1n)
Contoh: T(n) = 2T(n/2) + O(n) → T(n) = Θ(n log n)
KASUS 3
Combine mendominasi
f(n) = Ω(nlog_b(a)+ε)
T(n) = Θ(f(n))
Contoh: T(n) = T(n/2) + O(n) → T(n) = Θ(n)
Merge Sort
T(n) = 2T(n/2) + n
→ Θ(n log n) ✓
Binary Search
T(n) = T(n/2) + 1
→ Θ(log n) ✓
Strassen Matrix
T(n) = 7T(n/2) + n²
→ Θ(n2.81) ✓
Analisis Perbandingan

Perbandingan Kompleksitas Algoritma D&C

Algoritma Best Case Average Case Worst Case Space Stabil?
Merge Sort O(n log n) O(n log n) O(n log n) O(n) ✓ Ya
Quick Sort O(n log n) O(n log n) O(n²) O(log n) ✗ Tidak
Binary Search O(1) O(log n) O(log n) O(1) N/A
Strassen Matrix O(n²·⁸¹) O(n²·⁸¹) O(n²·⁸¹) O(n²) N/A

💡 Catatan: Strassen Matrix Multiplication lebih baik dari O(n³) naive, meski lebih rumit. Binary Search membutuhkan array sudah terurut sebagai prasyarat.

Evaluasi

Kelebihan & Kekurangan D&C

✅ Kelebihan

  • ▸
    Efisiensi tinggi — Sering mencapai O(n log n), jauh lebih baik dari O(n²) brute force untuk input besar
  • ▸
    Mudah diparalelkan — Submasalah independen dapat dijalankan di core prosesor berbeda secara bersamaan
  • ▸
    Modular & mudah diuji — Setiap fungsi rekursif dapat diuji secara terpisah
  • ▸
    Cache-friendly — Mengakses memori secara lokal, meningkatkan performa CPU cache

⚠️ Kekurangan

  • ▸
    Overhead rekursi — Setiap pemanggilan fungsi membutuhkan stack memory. Bisa menyebabkan Stack Overflow untuk n sangat besar
  • ▸
    Penggunaan memori lebih besar — Merge Sort membutuhkan O(n) space tambahan untuk array sementara
  • ▸
    Tidak efisien untuk masalah kecil — Overhead rekursi membuat D&C lebih lambat dari iterasi sederhana untuk n kecil
  • ▸
    Submasalah tidak boleh overlapping — Jika submasalah tumpang tindih, gunakan Dynamic Programming

⚡ Kapan pakai D&C? Ideal ketika masalah dapat dipecah menjadi submasalah independen yang serupa. Jika submasalah saling bergantung → gunakan Dynamic Programming.

Implementasi Nyata

Aplikasi Divide and Conquer

🔢

Perkalian Integer Besar

Algoritma Karatsuba memperkalikan dua bilangan n-digit dalam O(n^1.585) vs O(n²) naive. Digunakan di kriptografi RSA dan komputasi big number.

🎮

Computer Graphics

QuadTree & Octree mempartisi ruang 2D/3D secara rekursif untuk collision detection dan rendering di game engine (Unity, Unreal). Juga digunakan dalam image compression.

🌐

DNS Lookup

Sistem DNS menggunakan pencarian hierarkis rekursif — dari root server ke TLD server ke authoritative server, memecah domain "www.google.com" menjadi bagian-bagian kecil.

📊

Closest Pair Problem

Menemukan 2 titik terdekat dari n titik dalam O(n log n). Digunakan dalam pemetaan (GPS), robotika, dan analisis cluster data besar.

🧬

Bioinformatika

Algoritma BLAST untuk alignment sekuens DNA menggunakan D&C untuk membandingkan miliaran pasangan basa secara efisien dalam proyek Human Genome.

⚡

Fast Fourier Transform

FFT (Cooley-Tukey) membagi sinyal secara rekursif untuk transformasi dalam O(n log n). Digunakan di pemrosesan sinyal audio, kompresi MP3, dan 5G.

Perbandingan Paradigma

D&C vs Dynamic Programming vs Greedy

Aspek Divide & Conquer Dynamic Programming Greedy
Submasalah Independen Overlapping (tumpang tindih) Pilihan lokal optimal
Pendekatan Top-down rekursif Bottom-up / memoization Iteratif, pilih terbaik
Memori Stack rekursi Tabel memo/DP (besar) O(1) — minimal
Garansi optimal? Ya Ya Tidak selalu
Contoh Merge Sort, Quick Sort Fibonacci, Knapsack, LCS Dijkstra, Huffman, Kruskal

🔑 Kunci perbedaan: D&C = submasalah tidak tumpang tindih. DP = submasalah tumpang tindih + memoization. Greedy = keputusan lokal berulang tanpa rekursi penuh.

Pohon Rekursi

Memvisualisasikan Rekursi: Merge Sort n=8

Pohon Rekursi Merge Sort
[ 8 elemen ]              level 0
↙                                   ↘
[4 el][4 el]  level 1
↙↘↙↘
[2][2][2][2]level 2
↙↘↙↘↙↘↙↘
[1][1][1][1][1][1][1][1]L3
Level 0:1 × 8 elemen = 8 operasi merge
Level 1:2 × 4 elemen = 8 operasi merge
Level 2:4 × 2 elemen = 8 operasi merge
Level 3:8 × 1 elemen = base case
Total:3 × 8 = n × log₂(n) = n log n ✓

Mengapa O(n log n)?

  • ▸ Pohon rekursi memiliki log₂(n) level (setiap level membagi 2)
  • ▸ Setiap level memproses total n elemen (merge O(n))
  • ▸ Total: n × log n operasi = O(n log n)
  • ▸ Berlaku untuk best, average, dan worst case

Rekurens Formal

T(1) = Θ(1)
T(n) = 2T(n/2) + Θ(n)
a=2, b=2, f(n)=n, log₂(2)=1
f(n) = Θ(n^log₂(2)) → Kasus 2
∴ T(n) = Θ(n log n) ✓
Studi Kasus Tambahan

MinMaks — D&C vs Brute Force

Mencari nilai minimum dan maksimum secara bersamaan dalam satu array. D&C lebih efisien karena mengurangi jumlah perbandingan dari 2(n-1) menjadi ⌈3n/2⌉ - 2.

Contoh: A = [4, 12, 23, 9, 21, 1, 35, 2]
DIVIDE: [4,12,23,9] | [21,1,35,2]
CONQUER kiri: min=4, maks=23
CONQUER kanan: min=1, maks=35
COMBINE: min=1, maks=35 ✓
Brute Force: 14 perbandingan (2n-2)
D&C: 10 perbandingan (3n/2-2)
2(n-1)
Brute Force
⌈3n/2⌉-2
Divide & Conquer
// MinMaks dengan Divide & Conquer function MinMaks(A, l, r): // BASE CASE: 1 elemen if l == r: return (A[l], A[l]) // min=maks // BASE CASE: 2 elemen if r - l == 1: if A[l] < A[r]: return (A[l], A[r]) else: return (A[r], A[l]) // DIVIDE mid = (l + r) // 2 (min1, maks1) = MinMaks(A, l, mid) (min2, maks2) = MinMaks(A, mid+1, r) // COMBINE: 2 perbandingan saja min_total = min(min1, min2) maks_total = maks(maks1, maks2) return (min_total, maks_total) // T(n) = 2T(n/2) + 2 → O(n) // Perbandingan: ⌈3n/2⌉ - 2
Ringkasan Materi

Kesimpulan

Divide and Conquer adalah fondasi dari algoritma-algoritma paling efisien di dunia

🔪
DIVIDE
Bagi masalah menjadi submasalah lebih kecil
⚡
CONQUER
Selesaikan rekursif hingga base case
🔗
COMBINE
Gabungkan solusi submasalah menjadi solusi final
📊
ANALISIS
T(n)=aT(n/b)+f(n) → Master Theorem
3
Algoritma Utama Dibahas
Merge · Quick · Binary
O(n log n)
Kompleksitas Optimal
Merge Sort & Quick Sort (avg)
∞
Aplikasi di Dunia Nyata
DNS · FFT · GPU · Bio
Desain dan Analisis Algoritma · 2026
1 / 15