03 减治与变治算法

本章对应考试中的：V1 多数元素（2011影印 等，5 分）、V2 减治求 $\lfloor {\log }_{2}N\rfloor$（2020，4 分）、V3 减治求数组最小元素位置（HW1）、简答 Q1（二叉查找树属减治哪种变种、最差效率）、简答 Q2（AVL 树与 2-3 树的目的与效率）、作业 O1（约瑟夫斯问题非递推公式）。

---

核心考点

减治（decrease and conquer） 和 变治（transform and conquer） 是两类"把问题变简单再解"的策略，常考概念辨析（简答题）和具体算法设计（V1～V3）。

• 减治：把问题规模缩小一截，通常只解其中一个子问题（这是它与分治的关键区别——分治要解多个子问题）。
• 变治：先把输入或问题变个形式（排序、换数据结构、转成另一个问题），在新形式上更好解。

本章要能：说清减治/变治各自的几种变体；用变治法把多数元素从 $O(n^2)$ 优化到 $O(n)$；写出减治求对数、求最小元素的算法；答出 BST、AVL、2-3 树的概念题。

---

从零开始的前置知识

减治的三种变体

减治 按"每次规模缩小多少"分三种：

1. 减常数（decrease by a constant）：每次规模减去一个固定常数（通常减 1）。例：求 $n!$ 时 $n!=n\cdot (n-1)!$，规模每次减 1；约瑟夫斯问题每出局一人规模减 1。
2. 减常数因子（decrease by a constant factor）：每次规模除以一个固定常数（通常除以 2）。例：二分查找每次范围减半；求 $\lfloor {\log }_{2}N\rfloor$ 每次把 $N$ 除以 2。
3. 减可变规模（variable-size decrease）：每次缩小的量不固定。例：二叉查找树的查找（每步往左或右子树走，但两边子树大小可能很不一样）；求最大公约数的欧几里得算法。

变治的三种变体

变治 按"变什么"分三种：

1. 实例化简（instance simplification）：把输入预处理成同类型但更好处理的实例。最常见的是预排序（presorting）——先排序再求解。多数元素的变治法一就是这种。
2. 改变表示（representation change）：用另一种数据结构表示同样的数据。例：把普通二叉查找树改成 AVL 树 或 2-3 树 以保持平衡。
3. 问题化简（problem reduction）：把要解的问题转化成另一个已经知道怎么解的问题。例：求两数最小公倍数，转化为求最大公约数。

二分查找：减常数因子的样板

二分查找（binary search）：在一个已排好序的数组里找目标值 $x$。看正中间的元素：等于 $x$ 就找到；$x$ 比它小就只在左半找、比它大就只在右半找。每次范围减半，且只往一边走（只解一个子问题，所以是减治不是分治）。复杂度 $T(n)=T(n/2)+O(1)=O(\log n)$（详见 01_数学基础_渐进记号与递推式求解.md）。

---

逐题精解

V1 多数元素（2011影印 等，5 分）

原题：$A[1\dots n]$ 为整数序列，若整数 $a$ 在 $A$ 中出现次数多于 $\lfloor n/2\rfloor$，则 $a$ 称为多数元素。例如 $1,3,2,3,3,4,3$ 中 3 是多数元素（出现 4 次 $>\lfloor 7/2\rfloor =3$）。问蛮力算法复杂性如何？设计一个具有变治思想的算法提高效率，写出伪代码并分析时间复杂性。

蛮力法：对每个元素，数它在整个数组里出现多少次，看是否超过 $\lfloor n/2\rfloor$。两层循环，时间复杂度 $O(n^2)$。

变治法一：预排序，$O(n\log n)$（这是"实例化简"——先排序）。排序后，多数元素因为出现次数超过一半，必然占据连续的、长度超过 $\lfloor n/2\rfloor$ 的一段。扫描数组找最长的连续相等段即可：

Sort(A, n)                        // 排序，O(n log n)
i ← 0
while i < n:
    val ← A[i]; count ← 1
    while i+count < n and A[i+count] == val: count++
    if count > n/2: return val
    i ← i + count
return NONE                       // 不存在多数元素

复杂度由排序主导，$O(n\log n)$。

变治法二：Boyer–Moore 摩尔投票，$O(n)$（提示："任取两个不同的元素就同时丢弃"）。核心思想：维护一个"候选元素 $cand$"和一个"计数 $count$"。遇到和候选相同的就 count++，遇到不同的就 count--（相当于一个候选和一个非候选相互抵消）；count 减到 0 就换当前元素当新候选。因为多数元素比其它所有元素加起来还多，最后剩下的候选一定是它。

cand ← A[0]; count ← 0
for i ← 0 to n-1:
    if count == 0:        cand ← A[i]; count ← 1
    elif A[i] == cand:    count++
    else:                 count--          // 一对不同元素相互抵消
return cand              // 如需确认，再扫一遍数它是否真的 > n/2

演示（$A=[1,3,2,3,3,4,3]$）：

读到	1	3	2	3	3	4	3
操作	count0→候选1	3≠1，count0	count0→候选2	3≠2，count0	count0→候选3	4≠3，count0	count0→候选3
$cand$	1	1	2	2	3	3	3
$count$	1	0	1	0	1	0	1

最终候选 3，再扫一遍确认 3 出现 4 次 $>3$，确为多数元素。

复杂度 $O(n)$，只需一遍扫描、常数额外空间（用 Hash 表计数也是 $O(n)$ 时间，但要额外 $O(n)$ 空间，所以 试卷7 里说"Hash 不行"指的是空间不如摩尔投票省）。

---

V2 减治求 $\lfloor {\log }_{2}N\rfloor$（2020，4 分）

原题：写一个具有减治思想的求 $\lfloor {\log }_{2}N\rfloor$ 的算法，并推导其时间复杂性。

前置：$\lfloor x\rfloor$ 表示"向下取整"（不超过 $x$ 的最大整数）。$\lfloor {\log }_{2}N\rfloor$ 就是"$N$ 能被 2 连续整除多少次直到小于 2"，也等于"$N$ 的二进制表示的位数减 1"。

思路（减常数因子）：不断把 $N$ 整除 2 并计数，直到 $N<2$。每除一次规模减半。

DecLog2(N):
    k ← 0
    while N > 1:
        N ← N / 2          // 整数除法（规模减半，减治）
        k ← k + 1
    return k               // 即 ⌊log2 N⌋

演示（$N=20$）：$20\to 10\to 5\to 2\to 1$，共除 4 次，返回 $k=4$。验证：$2^4=16\le 20<32=2^5$，故 $\lfloor {\log }_{2}20\rfloor =4$ ✓。

复杂度：$T(N)=T(N/2)+O(1)$，循环执行 $\lfloor {\log }_{2}N\rfloor +1$ 次，时间复杂度 $O(\log N)$。

---

V3 减治求数组最小元素的位置（HW1）

原题：对求 $n$ 个实数数组中最小元素位置的问题，写出具有减治思想算法的伪代码，确定时间效率，并与蛮力算法比较。

思路：把数组对半分，分别求两半的最小元素及其下标，再取较小者对应的下标。

(element, index) = FindLeast(A, low, high):
    if low == high: return (A[low], low)              // 出口
    mid ← (low + high) / 2
    (e1, i1) = FindLeast(A, low, mid)
    (e2, i2) = FindLeast(A, mid+1, high)
    return (e1 < e2) ? (e1, i1) : (e2, i2)

复杂度：$T(n)=2T(n/2)+O(1)=O(n)$，与蛮力法（一遍扫描比较，也是 $O(n)$）同阶。

这道题的真正用意：虽然同为 $O(n)$，但这个递归版本要做约 $2n$ 次比较，常数因子更大，反而不如直接一遍扫描的蛮力法划算。它考的是让你体会"减治/分治不是万能的，要权衡常数因子"。（注意此解用了两个子问题，严格说更接近分治；题目意在用它说明思想与代价的权衡。）

---

简答 Q1：二叉查找树属减治哪种变种、最差效率（2011影印 等）

原题：二叉查找树属于减治策略三个变种中哪一个的应用？什么情况下表现出最差效率？此时查找和插入算法的复杂性如何？

前置：什么是二叉查找树。 二叉查找树（binary search tree, BST） 是一种二叉树，满足：任一结点的左子树所有值都比它小、右子树所有值都比它大。查找时从根开始，比当前结点小就往左、大就往右，类似二分查找。

答案：

• 二叉查找树属于减治策略中**"减去的规模可变（减可变规模）"** 变种的应用——每步往左或右子树走，但左右子树的大小可能很不一样。
• 当树严格歪斜、退化成一条链时表现最差（例如把已经有序的序列依次插入，每个新值都比前一个大，全部挂到右边，树变成一条"竖线"）。
• 此时查找和插入在最坏情况下的时间复杂度都是 $O(n)$（要从头走到尾，跟在数组里逐个找一样慢）。

---

简答 Q2：AVL 树与 2-3 树的目的与效率（2011影印 等，2 分）

原题：构造 AVL 树和 2-3 树的主要目的是什么？它们各自的查找和插入效率如何？

前置：上面说过普通 BST 会退化成链导致 $O(n)$。AVL 树 和 2-3 树 都是"自动保持平衡"的查找树（属变治中的"改变表示"）。平衡 指任何叶子到根的距离都差不多，树不会变得又细又长。

• AVL 树：一种自平衡二叉查找树，规定任一结点的左右子树高度差不超过 1，靠"旋转"操作维持平衡。
• 2-3 树：每个结点可以有 2 个或 3 个孩子，所有叶子在同一层，天然平衡。

答案：构造它们的主要目的是维持树的平衡、避免树退化成链，从而压低树高，使查找与插入更快。AVL 树的查找、插入效率均为 $O({\log }_{2}n)$；2-3 树的查找、插入效率也均为 $O({\log }_{2}n)$。

---

作业 O1：约瑟夫斯问题非递推公式（HW1）

原题：给出约瑟夫斯问题的非递推公式 $J(n)$ 并证明。$n$ 为最初总人数，$J(n)$ 为最后幸存者的最初编号（每报到 2 出局，即 $m=2$）。

前置：约瑟夫斯问题。 $n$ 个人围成一圈，从 1 号开始报数，每报到 2 的人出局，然后从下一个人继续报数，如此循环，直到只剩一人。$J(n)$ 就是最后那个幸存者最初的编号。

递推关系（减一治的思想，每出局一人规模减小）：

$$J(1)=1,J(2n)=2J(n)-1,J(2n+1)=2J(n)+1.$$

非递推闭式：把 $n$ 写成 $n=2^m+k$，其中 $2^m$ 是不超过 $n$ 的最大 2 的幂、$0\le k<2^m$，则

$$\boxed{{\displaystyle J(n)=2k+1}}.$$

怎么套用：先找出不超过 $n$ 的最大 2 的幂 $2^m$，算出余数 $k=n-2^m$，代入 $2k+1$ 即可。

演示（$n=10$）：不超过 10 的最大 2 的幂是 $2^3=8$，$k=10-8=2$，故 $J(10)=2\times 2+1=5$，即 5 号幸存。

等价说法：把 $n$ 写成二进制，$J(n)$ 就是把这串二进制循环左移一位得到的数。例如 $n=10=(1010{)}_2$，循环左移一位得 $(0101{)}_2=5$，与上面一致。

证明思路（数学归纳法）：对 $k$ 的奇偶分别代入递推式 $J(2n)=2J(n)-1$ 与 $J(2n+1)=2J(n)+1$，可验证若较小规模满足 $J=2k+1$，则较大规模也满足，加上基例 $J(1)=1$（此时 $k=0$，$2\cdot 0+1=1$），即得闭式成立。

推广（每报 $m$ 出局，了解即可）：$J(1,m)=0$，$J(n,m)=(J(n-1,m)+m)modn$（这里编号从 0 开始）。

---

高频陷阱 / 易错点小结

1. 减治 vs 分治：减治通常只解一个子问题，分治解多个。二分查找是减治，归并排序是分治。
2. BST 退化：按有序序列插入会退化成链，最坏 $O(n)$；这是 Q1 的考点。
3. 多数元素摩尔投票最后要再扫一遍验证候选是否真超过 $\lfloor n/2\rfloor$（若题目不保证一定存在多数元素）。
4. 多数元素的"变治"体现在哪：法一是预排序（实例化简），法二可视为对问题的巧妙变形；答题时点明"变治思想"。
5. 约瑟夫斯记住 $n=2^m+k\Rightarrow J(n)=2k+1$，别把 $2^m$ 找错（要"不超过 $n$ 的最大 2 的幂"）。

---

自测清单

• [ ] 说出减治三变体（减常数 / 减常数因子 / 减可变规模）各一个例子。
• [ ] 说出变治三变体（实例化简 / 改变表示 / 问题化简）各一个例子。
• [ ] 写出多数元素的摩尔投票伪代码，对 $[1,3,2,3,3,4,3]$ 跑出候选 3。
• [ ] 写出求 $\lfloor {\log }_{2}N\rfloor$ 的减治算法，对 $N=20$ 得 4。
• [ ] 答出 BST 属"减可变规模"、退化时查找/插入 $O(n)$。
• [ ] 答出 AVL、2-3 树目的（保持平衡）与效率 $O({\log }_{2}n)$。
• [ ] 写出约瑟夫斯闭式 $J(n)=2k+1$（$n=2^m+k$），并算 $J(10)=5$。