Divide and Conquer

Divide and conquer adalah paradigma algoritma yang bekerja dengan tiga langkah: divide (pecah jadi sub-masalah), conquer (selesaikan tiap sub-masalah, biasanya rekursif), dan combine (gabungkan hasilnya). Banyak algoritma klasik — merge sort, quick sort, binary search, closest pair — adalah implementasi paradigma ini. Pada Chapter ini kita akan membedah struktur umum divide and conquer, menyegarkan Master Theorem untuk analisis kompleksitas, dan menerapkannya pada satu contoh non-trivial: maximum subarray sum dengan strategi divide and conquer.

Tiga Langkah Paradigma #

Aturan #

Setiap algoritma divide and conquer memiliki struktur berikut:

solve(problem P):
  if (P cukup kecil):
      return solusi langsung             // base case
  (P1, P2, ..., Pk) = divide(P)          // pecah
  for each Pi:
      Si = solve(Pi)                      // conquer (rekursif)
  return combine(S1, S2, ..., Sk)         // combine

Mekanisme: Mengapa Bekerja #

Kompleksitas ditentukan oleh tiga parameter:

• T(n) — waktu untuk masalah ukuran n.
• a — jumlah sub-masalah yang dibuat.
• b — rasio ukuran sub-masalah terhadap masalah asli (sub-masalah ukuran n/b).
• f(n) — waktu untuk divide + combine.

Persamaan recurrences: T(n) = a · T(n/b) + f(n).

Master Theorem (Segar) #

Aturan #

Master Theorem memberi solusi tertutup untuk recurrences berbentuk T(n) = a · T(n/b) + f(n):

Contoh Penting #

Contoh: Maximum Subarray Sum (Divide and Conquer) #

Soal #

Diberikan array a berisi integer (boleh negatif), cari jumlah maksimum subarray kontigu. Subarray boleh kosong (jumlah 0).

Strategi D&C #

Bagi array menjadi dua bagian sama besar: left = a[0..mid], right = a[mid+1..n-1]. Maka subarray maksimum berada di salah satu dari:

1. Sepenuhnya di kiri → selesaikan rekursif di left.
2. Sepenuhnya di kanan → selesaikan rekursif di right.
3. Memotong titik tengah → menjorok ke kiri dari mid dan ke kanan dari mid+1. Cari “suffix maksimum” di kiri + “prefix maksimum” di kanan.

Kode: Implementasi D&C #

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

long long cross_sum(const std::vector<int>& a, int lo, int mid, int hi) {
    // Suffix maksimum dari a[lo..mid] berakhir di mid
    long long left_sum = 0, best_left = 0;
    for (int i = mid; i >= lo; --i) {
        left_sum += a[i];
        best_left = std::max(best_left, left_sum);
    }
    // Prefix maksimum dari a[mid+1..hi] dimulai di mid+1
    long long right_sum = 0, best_right = 0;
    for (int i = mid + 1; i <= hi; ++i) {
        right_sum += a[i];
        best_right = std::max(best_right, right_sum);
    }
    return best_left + best_right;
}

long long max_subarray(const std::vector<int>& a, int lo, int hi) {
    if (lo > hi) return 0;
    if (lo == hi) return std::max(0, a[lo]);
    int mid = lo + (hi - lo) / 2;
    long long left = max_subarray(a, lo, mid);
    long long right = max_subarray(a, mid + 1, hi);
    long long cross = cross_sum(a, lo, mid, hi);
    return std::max({left, right, cross});
}

long long max_subarray(const std::vector<int>& a) {
    if (a.empty()) return 0;
    return max_subarray(a, 0, static_cast<int>(a.size()) - 1);
}

int main() {
    std::vector<std::vector<int>> tests = {
        {-2, 1, -3, 4, -1, 2, 1, -5, 4},
        {1, 2, 3, 4, 5},
        {-1, -2, -3, -4},
        {5, -2, 3, 4, -1, 7, -8, 2, 1}
    };
    for (const auto& a : tests) {
        std::cout << "max subarray = " << max_subarray(a) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

max subarray = 6
max subarray = 15
max subarray = 0
max subarray = 16

1. Fungsi cross_sum: menghitung jumlah subarray yang memotong titik tengah. Subarray ini berbentuk a[i..j] dengan i ≤ mid < j.
2. Baris for (int i = mid; i >= lo; --i): iterasi dari mid ke kiri, mengakumulasi suffix. Simpan nilai maksimum best_left.
3. Baris for (int i = mid + 1; i <= hi; ++i): iterasi dari mid+1 ke kanan, mengakumulasi prefix. Simpan nilai maksimum best_right.
4. Baris return best_left + best_right;: subarray melintasi tengah = suffix maks kiri + prefix maks kanan.
5. Baris int mid = lo + (hi - lo) / 2;: hindari overflow lo + hi. Base case lo == hi mengembalikan max(0, a[lo]) (subarray boleh kosong).
6. Baris long long cross = cross_sum(a, lo, mid, hi);: hitung subarray yang melintasi tengah.
7. Baris return std::max({left, right, cross});: jawaban adalah maksimum dari tiga kemungkinan.
8. Hasil 6 untuk {-2,1,-3,4,-1,2,1,-5,4}: subarray {4,-1,2,1} = 6. Sesuai (ini soal LeetCode klasik).
9. Hasil 0 untuk {-1,-2,-3,-4}: semua negatif, pilih subarray kosong → 0.
10. Hasil 16 untuk {5,-2,3,4,-1,7,-8,2,1}: subarray {5,-2,3,4,-1,7} = 16. Sesuai.

Divide and Conquer pada Segment Tree #

Salah satu penggunaan D&C yang sangat praktis adalah segment tree — pohon biner di mana setiap node menyimpan agregat dari sebuah rentang. Struktur ini memungkinkan query rentang dalam O(log n). Pembangunan pohon awal adalah D&C murni: bagi array, rekursif ke kiri-kanan, gabungkan.

Setiap query “jumlah elemen di [l, r]” dijawab dengan menyusuri O(log n) node yang persis menutupi rentang tersebut.

Ringkasan #

• Divide and conquer = divide → conquer (rekursif) → combine. Base case menangani masukan kecil.
• Master Theorem: untuk T(n) = a·T(n/b) + f(n), solusi bergantung pada perbandingan f(n) dengan n^(log_b a).
• Merge sort dan binary search adalah contoh kanonik D&C; keduanya mengikuti pola “bagi dua, rekursif, gabung”.
• Contoh maximum subarray via D&C menghasilkan O(n log n), lebih lambat dari Kadane O(n) tetapi merupakan dasar untuk segment tree.
• Segment tree adalah D&C statis yang siap pakai untuk range query — kuasai pola umumnya untuk soal-soal lanjutan.