分治演算法（Divide and Conquer）#

分治法是遞迴的高階應用，核心思想是庖丁解牛（Chunk it up）：將大問題拆解為若干個互不相關的子問題，分別解決後合併結果。

分治三步驟#

1. Divide（分）：將大問題拆解成若干個子問題
2. Conquer（治）：分別解決這些子問題
3. Merge（合）：將子問題的結果合併成原問題的解

這與分散式系統中的 MapReduce 思想如出一轍。

分治程式碼模板#

fun divideConquer(problem: Problem?): Result {
    // 1. Terminator (終止條件)
    if (problem == null) {
        return baseResult
    }

    // 2. Prepare & Split (準備資料/拆分問題)
    val data = prepareData(problem)
    val subProblems = splitProblem(problem, data)

    // 3. Conquer Subproblems (解決子問題)
    val subResults = subProblems.map { divideConquer(it) }

    // 4. Merge (合併結果)
    val result = merge(subResults)

    // 5. Revert States (清理狀態，如需要)
    return result
}

分治的適用條件#

分治法適用的前提是子問題互不相關。如果子問題有重疊（如費氏數列），則不應使用標準分治，而應考慮動態規劃。

經典案例#

Pow(x, n) ^↗：快速冪#

計算 x 的 n 次方。

分治邏輯：

• 若 n 為偶數：x^n = (x^(n/2))^2
• 若 n 為奇數：x^n = (x^(n/2))^2 * x

n 可能是負數，需先將 x 轉為 1/x，n 轉為正數。

fun myPow(x: Double, n: Int): Double {
    var base = x
    // 用 Long 承接指數，避免 n = Int.MIN_VALUE 取負號時溢位
    var exp = n.toLong()
    if (exp < 0) {
        base = 1 / base
        exp = -exp
    }

    var result = 1.0
    while (exp > 0) {
        if (exp and 1L == 1L) {  // 最後一位是 1
            result *= base
        }
        base *= base    // 基底翻倍
        exp = exp shr 1 // 右移一位
    }
    return result
}

求眾數：分治求多數元素 ^↗#

找出陣列中出現次數大於 n/2 的元素。

分治邏輯：

1. Divide：將陣列切分為左右兩半
2. Conquer：遞迴求出左右兩邊的眾數
3. Merge：
   • 若左右眾數相同，直接返回
   • 若不同，計算兩者在當前區間的出現次數，返回較多者

fun majorityElement(nums: IntArray): Int {
    fun countInRange(target: Int, lo: Int, hi: Int): Int {
        var count = 0
        for (i in lo..hi) {
            if (nums[i] == target) count++
        }
        return count
    }

    fun majority(lo: Int, hi: Int): Int {
        // 終止條件：區間長度為 1
        if (lo == hi) return nums[lo]

        // 分
        val mid = lo + (hi - lo) / 2
        val left = majority(lo, mid)
        val right = majority(mid + 1, hi)

        // 合
        if (left == right) return left

        // 計數比較
        val leftCount = countInRange(left, lo, hi)
        val rightCount = countInRange(right, lo, hi)
        return if (leftCount > rightCount) left else right
    }

    return majority(0, nums.size - 1)
}

分治 vs 遞迴#

分治法的子問題之間沒有依賴關係，因此非常適合平行計算（Parallel Processing）。

分治天生適合平行化：從合併排序到 MapReduce#

分治的精髓是把大問題拆成彼此獨立的子問題，各自解完再合併。這個「獨立」不只是程式設計上的乾淨，更是性能上的金礦：正因為子問題之間沒有依賴，它們可以同時丟到不同的核心、不同的機器上一起算，最後再把結果拼起來。

記住這條因果鏈：子問題獨立 ➡️ 可平行。一個演算法能不能輕鬆平行化，第一個要看的就是它的子問題之間有沒有資料依賴。分治幾乎自帶這個性質。

幾個直觀的例子：

• 合併排序：就像把一疊牌分給好幾個人，每人各排好手上那一疊（互不干擾），再兩兩合併成有序的大疊。各人排序的階段完全可以同時進行。
• 矩陣乘法：結果矩陣的每一塊（行/列切塊）都能獨立算出，自然可以切成許多小任務分給多台機器。

而 MapReduce 的本質，就是把分治搬到了分散式叢集上：

差別只在於：MapReduce 額外把任務調度、負載均衡、容錯（節點掛掉自動重跑） 全都自動化了。換句話說，當你理解了分治的「拆—算—合」，你其實已經理解了 MapReduce 的骨架。

一道題、四種複雜度：最大子陣列和 ^↗的演算法階梯#

「最大子陣列和」（給一個含正負數的陣列，找出總和最大的連續區間）是一道極佳的教學題——因為同一個問題，可以用四種層次完全不同的思路解出來，剛好串起了演算法設計的階梯。

這道題的線性解，曾在一場研討會上被人聽完題目後一分鐘內口頭給了出來，把原本需要跑十幾天的計算壓到幾毫秒。它最好地說明了一件事：選對演算法，遠勝於拼命微調——常數級的硬體加速永遠追不上一個降階的演算法。

分治版怎麼做#

這是分治章，重點放在 O(n log n) 的分治解。把陣列從中間切開後，最大子陣列只可能落在三種位置之一：

1. 完全在左半：遞迴求左半的最大子陣列和。
2. 完全在右半：遞迴求右半的最大子陣列和。
3. 跨越中點：這段必定「同時包含中點左右」，所以從中點向左掃出最大和、向右掃出最大和，兩者相加即為跨中點的最大和。

三者取最大，就是當前區間的答案。

fun maxSubArray(nums: IntArray): Int {
    fun divide(lo: Int, hi: Int): Int {
        // 終止條件：單一元素
        if (lo == hi) return nums[lo]

        val mid = lo + (hi - lo) / 2

        // 1 & 2：左半最大、右半最大
        val leftMax = divide(lo, mid)
        val rightMax = divide(mid + 1, hi)

        // 3：跨中點最大（必含 mid 與 mid+1）
        var leftBest = Int.MIN_VALUE
        var s = 0
        for (i in mid downTo lo) {
            s += nums[i]
            leftBest = maxOf(leftBest, s)
        }
        var rightBest = Int.MIN_VALUE
        s = 0
        for (i in mid + 1..hi) {
            s += nums[i]
            rightBest = maxOf(rightBest, s)
        }
        val crossMax = leftBest + rightBest

        // 三者取大
        return maxOf(leftMax, rightMax, crossMax)
    }

    return divide(0, nums.size - 1)
}

遞迴式為 $T(n) = 2T(n/2) + O(n)$，由主定理得 $O(n \log n)$——與合併排序同階。

再往上一階的 O(n) 掃描解（Kadane）其實是動態規劃：以「必須以第 i 個元素結尾」為狀態，邊掃邊更新。它與分治版的詳細對照，見 動態規劃的子陣列問題。