分治模板
从归并排序中提炼出三步模板（拆分、解决、合并），并将其系统地应用到新的问题形式中。
分治模板 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是分治法
分治法通过将问题拆分为同类型的独立子问题，递归解决每个子问题，然后组合它们的解来解决问题。关键在于“独立”——子问题之间不共享状态（不同于彼此重叠的 DP）。经典示例包括归并排序、二分查找、快速排序、最近点对和快速矩阵乘法。分治法通常通过三步模板达到 O(n log n) 时间复杂度。
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]三步模板
每个分治法算法都遵循三个步骤：(1) 分解 — 将问题拆分为两个（或更多）较小的子问题，通常在中点处进行。(2) 解决 — 递归解决每个子问题。定义基本情况以终止递归（通常为 n ≤ 1）。(3) 合并 — 将子问题的解合并为整体解。创造性完全体现在合并步骤中；分解通常只是从中点处拆分。
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)归并排序作为经典示例
归并排序完美展示了分治法：分解 — 在中点处分割数组。解决 — 递归地对两半进行排序。合并 — 在 O(n) 时间内将两个有序部分合并。the merge 步骤是所有工作发生的地方。递推式：T(n) = 2T(n/2) + O(n)。根据主定理情况 2：T(n) = O(n log n)。这是最重要的分治法递推式，务必记住。
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]主定理速查
主定理用于求解形如 T(n) = aT(n/b) + f(n) 的递推式：情况 1：f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a))。情况 2：f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n)。情况 3：f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n))。归并排序：a=2，b=2，f(n)=O(n)，n^log_2(2)=n → 情况 2 → O(n log n)。
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)最大子数组：分治法方法
最大子数组的分治法方法是：答案要么完全位于左半部分，要么完全位于右半部分，要么跨越中点。对于跨越中点的情况，从 mid 向左、从 mid+1 向右扩展，分别取得两个方向上的最大和，然后进行合并。这种 O(n log n) 的分治法比 O(n) 的卡丹算法更慢，但能够很好地展示 the 模板，也是常见的分治法面试题。
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6幂函数：快速幂
快速幂（LeetCode 50）使用分治法在 O(log n) 时间内计算 x^n。当 n 为偶数时：x^n = (x^(n/2))^2。当 n 为奇数时：x^n = x × x^(n-1)。使用 x^(-n) = 1/x^n 处理负数 n。每次递归调用都会将 n 减半，因此递归深度为 O(log n)。这是一个简洁的示例，其中合并步骤只是乘法——简单却有效。
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1将有序数组转换为 BST
将有序数组转换为 BST（LeetCode 108）使用分治法：选择中点作为根节点（确保高度平衡），从左半部分递归构建左子树，从右半部分递归构建右子树。这样会生成一棵高度平衡的 BST，其最小高度为 O(log n)。分治法结构与二分查找相似——递归的每一层都将中点指定为当前子范围的根节点。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)何时不应优先选择分治法
分治法存在开销：函数调用栈深度、数组切片（如果不使用索引）以及合并步骤。当合并步骤为 O(n) 或更低时，分治法通常是最优的。当子问题重叠时，分治法会浪费地重复计算解——这时需要使用 DP。当合并步骤占主导地位（例如为 O(n²)）时，分治法并不会比朴素方法更好。请了解如何选择：独立子问题使用分治法，重叠子问题使用 DP。
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!对有序矩阵进行分治法二分查找
在二维矩阵中搜索（LeetCode 240）时，如果每一行和每一列都已排序，可以使用分治法：从右上角开始。如果当前值 > 目标值，则向左移动（排除一列）。如果当前值 < 目标值，则向下移动（排除一行）。如果相等，则找到了目标。这个 O(m+n) 算法严格来说不是递归分治法，但共享了 the 关键思想：每一步都排除一半搜索空间。
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # False递归树分析
对于不符合主定理的分治法递推式，请使用递归树方法。画出每一层递归调用，并累加每层的工作量。归并排序：在第 k 层有 2^k 个大小为 n/2^k 的子问题。每层的工作量 = 2^k × O(n/2^k) = O(n)。总层数 = log n。总工作量 = O(n log n)。这种可视化方法适用于任何递推式，有助于理解分治法通常为何能达到 O(n log n)。
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')分治法面试沟通
在面试中介绍分治法解法时：(1) 明确陈述三个步骤：“我将在中点处分解，递归解决两半，然后通过合并完成组合。”(2) 清楚地指出基本情况。(3) 推导递推式：T(n) = 2T(n/2) + O(n)。(4) 应用主定理或递归树推导出 O(n log n)。(5) 说明分治法何时比替代方案更好或更差（重叠子问题使用 DP，最大子数组使用卡丹算法）。
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')快速检查
测试您对本课“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学到了：分治法遵循 the 模板：基本情况 → 在中点处分解 → 递归解决 → 合并，T(n) = 2T(n/2) + O(n) 根据主定理情况 2 得出 O(n log n)，以及分治法适用于独立子问题，而当子问题重叠时则需要 DP。接下来我们将使用修改版归并排序，应用分治法统计数组中的逆序对。
常见问题解答
「分治模板」课时是免费的吗？
是的 — 「分治模板」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「分治模板」这节课中我会学到什么？
从归并排序中提炼出三步模板（拆分、解决、合并），并将其系统地应用到新的问题形式中。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「分治模板」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。