分治与归并计数 · HTML
数学 / 逻辑形态
T(n)=aT(n/b)+C(n)。split 定义子域，solve 返回最小充分摘要，combine 由子摘要构造父答案；基础规模直接求解。
识别信号
- 输入有自然中点、空间分区或层级。
- 子区域内部可独立解决且交叠很少。
- 跨边界贡献可高效合并。
- 子问题与原问题同型且规模显著缩小。
- 希望利用递归层级实现排序、计数或并行。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 子问题大量重叠 | 同一状态反复出现时应 memoization/DP，纯分治会指数重复。 |
| combine 比原问题还难 | 若每层合并重新做 O(n²)，拆分未带来收益。 |
| 仅仅用了递归 | 递归是控制流；分治还需独立子问题与明确合并契约。 |
核心不变量
solve(lo,hi) 返回该子域完整且符合约定的摘要；combine 只依赖子摘要，并使每个跨子域贡献恰计一次。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前半开子域 [lo,hi)、其返回摘要，以及可复用的临时缓冲。 |
| Transition | base case 直接返回；否则 split，递归求子摘要，再 combine。 |
| Frontier / order | 递归栈上的待求解/待合并子域，通常按 postorder 完成。 |
Python 骨架
def divide_solve(items):
def solve(lo, hi):
if hi - lo <= 1:
return items[lo:hi]
mid = lo + (hi - lo) // 2
left = solve(lo, mid)
right = solve(mid, hi)
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
return merged + left[i:] + right[j:]
return solve(0, len(items))
正确性思路
- 基础规模按定义正确。
- 归纳假设每个子调用返回其子域完整摘要。
- combine 契约保留内部答案并补齐跨边界贡献，所以父域正确；归纳至根。
复杂度
| Time | Space | Parameters |
|---|
| 由 T(n)=aT(n/b)+C(n) 决定；二分加线性合并为 O(n log n) | 典型 O(n) 缓冲 + O(log n) 栈 | a 为子问题数，b 为缩小因子，C(n) 为合并成本。 |
边界条件
- 空输入
- 单元素 base case
- 半开区间与 mid
- 奇数长度
- 递归深度
- 跨边界重复计数
错误模式
| Pattern | Why it fails / fix |
|---|
| 区间约定混乱 | 统一 [lo,hi)，base 为 hi-lo<=1，避免 mid 重叠或遗漏。 |
| 每层切片复制 | 可能放大空间与常数；性能敏感时传边界并复用 buffer。 |
| 未定义返回契约 | 父层不知道子摘要语义，combine 必然脆弱。 |
| 错误套 Master Theorem | 子问题不均或成本不规则时应画递归树分析。 |
选择与排除规则
- 先写 solve 的返回摘要，再写 split。
- 确认 combine 比直接求解便宜。
- 重叠显著则转 memo/DP。
- 固定 [lo,hi) 与 base case。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 每层总合并 O(7)，共有约 log 7 层。 |
| Setup | 把 7 个读数按位置分成左右两半并排序。 |
| Trace | 递归让两半有序，合并只比较各自尚未消费的最小头部。 |
Recall prompts
我的补充