Dua chapter terakhir memberi kita dua strategi yang berlawanan arah: menjelajah semua kemungkinan, atau langsung menebak pilihan terbaik tanpa kembali. Divide and conquer menawarkan jalan tengah yang tenang: pecah masalah menjadi dua versi kecil dari dirinya, selesaikan masing-masing, lalu gabungkan hasilnya. Kita sebenarnya sudah memakainya tanpa memberi nama — merge sort, binary search, dan traversal tree semuanya divide and conquer. Chapter ini memformalkan pola tiga langkahnya, menjadikan merge sort templatnya, lalu menaklukkan masalah yang belum kita sentuh: mencari subarray dengan jumlah terbesar, yang diselesaikan tiga kali dengan tiga strategi berbeda.

Tiga Langkah: Bagi, Selesaikan, Gabungkan #

Semua algoritma divide and conquer mengikuti kerangka yang sama:

  • Bagi (divide): pecah input berukuran n menjadi dua bagian sekitar setengah ukuran di titik tengah.
  • Selesaikan (conquer): panggil fungsi yang sama secara rekursif pada kedua bagian; bila ukuran sudah cukup kecil (biasanya satu elemen), jawab langsung.
  • Gabung (combine): susun jawaban kedua bagian menjadi jawaban utuh.

Biayanya mengikuti rumus perulangan (recurrence) T(n) = 2T(n/2) + O(n) — dua panggilan setengah ukuran ditambah pekerjaan penggabungan linear — yang hasil akhirnya O(n log n). Syarat pentingnya: kedua subproblem harus saling lepas. Begitu subproblem tumpang-tindih dan saling mengulang, strategi ini memboroskan tenaga, dan kita akan melihat obatnya di chapter Dynamic Programming.

Merge Sort sebagai Templat #

Program berikut dimulai dengan merge sort lengkap (recap dari chapter Sorting Algorithms, kali ini diberi label BAGI dan GABUNG), lalu berpindah ke studi kasus barunya:

cpp 
// Divide and conquer: recap merge sort dan max subarray tiga cara.
#include <iostream>
#include <vector>

// --- Bagi-selesaikan-gabung: merge sort (recap dari chapter sorting) ---
void merge(std::vector<int>& data, int kiri, int tengah, int kanan,
           std::vector<int>& bantu, long long& perbandingan) {
    int i = kiri, j = tengah + 1, k = kiri;
    while (i <= tengah && j <= kanan) {
        ++perbandingan;
        if (data[i] <= data[j]) bantu[k++] = data[i++];
        else                    bantu[k++] = data[j++];
    }
    while (i <= tengah) bantu[k++] = data[i++];
    while (j <= kanan)  bantu[k++] = data[j++];
    for (int t = kiri; t <= kanan; ++t) data[t] = bantu[t];
}

void mergeSort(std::vector<int>& data, int kiri, int kanan,
               std::vector<int>& bantu, long long& perbandingan) {
    if (kiri >= kanan) return;  // basis: 0/1 elemen sudah terurut
    int tengah = kiri + (kanan - kiri) / 2;
    mergeSort(data, kiri, tengah, bantu, perbandingan);      // BAGI kiri
    mergeSort(data, tengah + 1, kanan, bantu, perbandingan); // BAGI kanan
    merge(data, kiri, tengah, kanan, bantu, perbandingan);   // GABUNG
}

// --- Max subarray dengan divide and conquer ---
struct Hasil {
    long long jumlah;
    int lo, hi;
};

// Subarray terbaik yang MENYEBERANGI titik tengah.
Hasil maxSilang(const std::vector<int>& a, int lo, int mid, int hi) {
    long long jumlah = 0, kiriTerbaik = 0;
    int idxKiri = mid;
    for (int i = mid; i >= lo; --i) {
        jumlah += a[i];
        if (i == mid || jumlah > kiriTerbaik) { kiriTerbaik = jumlah; idxKiri = i; }
    }
    jumlah = 0;
    long long kananTerbaik = 0;
    int idxKanan = mid + 1;
    for (int j = mid + 1; j <= hi; ++j) {
        jumlah += a[j];
        if (j == mid + 1 || jumlah > kananTerbaik) { kananTerbaik = jumlah; idxKanan = j; }
    }
    return {kiriTerbaik + kananTerbaik, idxKiri, idxKanan};
}

Hasil maxSubarrayDC(const std::vector<int>& a, int lo, int hi, long long& panggilan) {
    ++panggilan;
    if (lo == hi) return {a[lo], lo, hi};  // basis: satu elemen
    int mid = lo + (hi - lo) / 2;
    Hasil kiri   = maxSubarrayDC(a, lo, mid, panggilan);
    Hasil kanan  = maxSubarrayDC(a, mid + 1, hi, panggilan);
    Hasil silang = maxSilang(a, lo, mid, hi);
    if (kiri.jumlah >= kanan.jumlah && kiri.jumlah >= silang.jumlah) return kiri;
    if (kanan.jumlah >= silang.jumlah) return kanan;
    return silang;
}

// --- Max subarray dengan Kadane O(n): satu lintasan saja ---
Hasil kadane(const std::vector<int>& a) {
    long long berjalan = a[0], terbaik = a[0];
    int lo = 0, hi = 0, mulai = 0;
    for (int i = 1; i < static_cast<int>(a.size()); ++i) {
        if (berjalan < 0) {  // prefix negatif hanya memberatkan: mulai ulang
            berjalan = 0;
            mulai = i;
        }
        berjalan += a[i];
        if (berjalan > terbaik) {
            terbaik = berjalan;
            lo = mulai;
            hi = i;
        }
    }
    return {terbaik, lo, hi};
}

// --- Pembanding: brute force O(n^2) ---
Hasil maxSubarrayBrute(const std::vector<int>& a) {
    Hasil terbaik{a[0], 0, 0};
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        long long jumlah = 0;
        for (int j = i; j < static_cast<int>(a.size()); ++j) {
            jumlah += a[j];
            if (jumlah > terbaik.jumlah) terbaik = {jumlah, i, j};
        }
    }
    return terbaik;
}

void cetakHasil(const char* label, const Hasil& h, const std::vector<int>& a) {
    std::cout << label << h.jumlah << " -> ";
    for (int i = h.lo; i <= h.hi; ++i) {
        if (i > h.lo) std::cout << ' ';
        std::cout << a[i];
    }
    std::cout << '\n';
}

int main() {
    // Bagian 1: merge sort sebagai contoh divide and conquer paling klasik.
    std::vector<int> acak = {38, 27, 43, 3, 9, 82, 10};
    std::vector<int> bantu(acak.size());
    long long perbandingan = 0;
    mergeSort(acak, 0, static_cast<int>(acak.size()) - 1, bantu, perbandingan);
    std::cout << "Merge sort 7 elemen: ";
    for (std::size_t i = 0; i < acak.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << acak[i];
    }
    std::cout << "  (" << perbandingan << " perbandingan merge)\n";

    // Bagian 2: max subarray dengan tiga pendekatan pada data yang sama.
    std::vector<int> pasar = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Hasil brute = maxSubarrayBrute(pasar);
    long long panggilan = 0;
    Hasil dc = maxSubarrayDC(pasar, 0, static_cast<int>(pasar.size()) - 1,
                             panggilan);
    Hasil kd = kadane(pasar);
    std::cout << "Max subarray dari {-2,1,-3,4,-1,2,1,-5,4}:\n";
    cetakHasil("  brute force O(n^2) : ", brute, pasar);
    cetakHasil("  divide and conquer : ", dc, pasar);
    std::cout << "    (" << panggilan << " pemanggilan fungsi rekursif)\n";
    cetakHasil("  Kadane O(n)        : ", kd, pasar);
    return 0;
}

Output yang Dihasilkan:

text 
Merge sort 7 elemen: 3 9 10 27 38 43 82  (14 perbandingan merge)
Max subarray dari {-2,1,-3,4,-1,2,1,-5,4}:
  brute force O(n^2) : 6 -> 4 -1 2 1
  divide and conquer : 6 -> 4 -1 2 1
    (17 pemanggilan fungsi rekursif)
  Kadane O(n)        : 6 -> 4 -1 2 1

Bedah baris penting:

  1. Baris 19-26 (mergeSort): tiga langkah dalam tujuh baris — basis rekursi, dua panggilan BAGI, satu pemanggilan GABUNG.
  2. Baris 29-33 (Hasil): struct yang membawa jawaban lengkap: jumlah terbaik beserta indeks awal dan akhirnya, supaya tiga algoritma bisa dibandingkan dengan adil.
  3. Baris 35-50 (maxSilang): bagian paling mudah terlewat — subarray terbaik yang menyeberangi titik tengah. Ia menyebar ke kiri dari mid dan ke kanan dari mid + 1, mengambil akumulasi terbaik di kedua sisi.
  4. Baris 52-62 (maxSubarrayDC): jawaban adalah terbesar dari tiga kandidat: subarray terbaik sepenuhnya di kiri, sepenuhnya di kanan, atau yang melintasi tengah.
  5. Baris 65-81 (kadane): pendekatan sekali-lintas: akumulasi berjalan direset begitu bernilai negatif, karena prefix negatif hanya memberatkan sisa deret.
  6. Baris 84-94 (maxSubarrayBrute): pembanding O(n²) yang mencoba semua pasangan batas — benar pasti, lambat pasti.

Studi Kasus: Max Subarray Tiga Cara #

Masalah max subarray berbunyi: dari deret bilangan bermacam tanda, temukan rentang berurutan dengan jumlah terbesar. Pada deret semacam perubahan harga harian, rentang itulah periode keuntungan terbaik. Ketiga algoritma di program tiba pada jawaban yang sama — jumlah 6 dari 4 -1 2 1 — tetapi dengan cara berbeda: brute force menguji semua pasangan batas pada O(n²); divide and conquer memecah deret dan menjawab tiga kandidat pada O(n log n); Kadane menyapu sekali pada O(n).

Angka 17 pada output adalah jumlah pemanggilan fungsi rekursif divide and conquer untuk sembilan elemen — persis 2n - 1, karena setiap pemanggilan membelah dan daunnya menyentuh setiap elemen sekali. Kadane memang unggul untuk masalah khusus ini, tetapi ia tidak bisa digeneralisasi; divide and conquer bisa diadaptasi untuk banyak masalah lain yang polanya serupa. Inilah perbandingan yang sehat: pendekatan umum sebagai fondasi berpikir, pendekatan khusus sebagai opsi percepatan.

Kapan Pola Ini Menguntungkan #

Divide and conquer layak dipilih ketika masalah punya struktur rekursif alami dan penggabungan hasilnya bisa dikerjakan cepat. Bonusnya sering terlupakan: karena dua separuh bekerja saling lepas, algoritma ini memparalelisasi dengan alami — separuh kiri dan kanan bisa berjalan pada thread berbeda. Batasnya juga sudah kita singgung: begitu subproblem mulai tumpang-tindih, pekerjaan berulang menumpuk dengan cepat.

Pertanyaan “bagaimana kalau subproblem memang tumpang-tindih” membawa kita ke topik berikutnya. Dynamic programming adalah divide and conquer yang memasang ingatan: setiap subproblem dihitung sekali, disimpan, dan dipakai ulang — dan selisih performanya bisa berorde ribuan kali lipat.

Rujukan resmi: std::vector dan std::size_t .