第二部分：基于规模的策略：分解与变换 (Structure Decomposition)

2.1 分治法

2.1.1 分而治之

分治的基本逻辑是将原始问题分解为若干子问题，在逐个解决各
个子问题的基础上，得到原始问题的解。那么最基础的，根据如何由分解出的子问题得出原始问题的解，
分治策略可分为两种情形：

原始问题的解只存在于分解出的某一个（或某几个）
子问题中，则只需要在这一（或这几个）子问题中求
解即可
原始问题的解需要由各个子问题的解再经过综合处理
得到

同时寻找最大值和最小值：

直接算法是

1. x ← A[1]; y ← A[1]
2. for i ← 2 to n
3.    if A[i] < x then x ← A[i]
4.    if A[i] > y then y ← A[i]
5. end for
6. return (x, y)

总比较次数为$2(n-1) = 2n - 2$。

如果利用分支思想将数组对半分割，分别求出左右两半的最大最小值，再进行合并。

Algorithm MINMAX (low, high)
1. if high – low = 1 then  // Base case: only 2 elements
2.    if A[low] < A[high] then return (A[low], A[high])
3.    else return (A[high], A[low])
4. else
5.    mid ← ⌊(low + high) / 2⌋
6.    (x1, y1) ← MINMAX (low, mid)       // recursively slove the left half
7.    (x2, y2) ← MINMAX (mid + 1, high)   // recursively solve the right half
8.    x ← min {x1, x2}                   
9.    y ← max {y1, y2}                   // merge
10.   return (x, y)
11. end if

根据代码可得递推关系式：

当 $n = 2$ 时，$C(2) = 1$
当 $n > 2$ 时，$C(n) = 2C(n/2) + 2$

解得$C(n) = \frac{3n}{2} - 2$

二分搜索（binary search）

递归版本

Algorithm BINARYSEARCH (low, high)
1. if low > high then return 0
2. else
3.    mid ← ⌊(low + high) / 2⌋
4.    if x = A[mid] then return mid
5.    else if x < A[mid] then return BINARYSEARCH (low, mid-1)
6.    else return BINARYSEARCH (mid + 1, high)
7. end if

对于最坏情况，即当 $x$ 不在数组中时
有递推公式

$C(1) = 1$
$C(n) \le 1 + C(\lfloor n/2 \rfloor)$，当 $n \ge 2$ 时。
解得$C(n) \le \lfloor \log n \rfloor + 1$，因此有时间复杂度$O(\log n)$。

循环结构可以避免递归调用产生的栈空间开销：

Algorithm BINARYSEARCH (low, high)
1. low ← 1; high ← n; j ← 0
2. while (low <= high) and (j = 0)
3.    mid ← ⌊(low + high) / 2⌋
4.    if x = A[mid] then j ← mid
5.    else if x < A[mid] then high ← mid - 1
6.    else low ← mid + 1
7. end while
8. return j

本质上是不断维护low和high两个指针。

由于递归调用栈，空间复杂度为 $O(\log n)$。非递归版本仅使用常数个辅助变量，空间复杂度为 $\Theta(1)$。

合并排序（Merge Sort）

合并排序比堆排序理解起来简单得多。其过程包括三个步骤：

分解：将待排序数组对半分成两个子数组。
治理：分别对两个子数组进行递归排序。
合并：将两个已排序的子数组合并为一个有序数组。

Algorithm MERGESORT (A, low, high)
1. if low < high then
2.    mid ← ⌊(low + high) / 2⌋
3.    mergesort(A, low, mid)      
4.    mergesort(A, mid + 1, high) 
5.    MERGE(A, low, mid, high)    
6. end if

Algorithm MERGE (A, low, mid, high)
   i ← low      // 左子数组指针
   j ← mid + 1  // 右子数组指针
   k ← low      // 辅助数组 B 的指针
   B ← copy of A // 或分配临时数组

   while i ≤ mid and j ≤ high do
       if A[i] ≤ A[j] then
           B[k] ← A[i]
           i ← i + 1
       else
           B[k] ← A[j]
           j ← j + 1
       end if
       k ← k + 1
   end while

   while i ≤ mid do
       B[k] ← A[i]
       k ← k + 1; i ← i + 1
   end while
   
   while j ≤ high do
       B[k] ← A[j]
       k ← k + 1; j ← j + 1
   end while

   for k ← low to high do
       A[k] ← B[k]
   end for

通用递推公式
对于递推方程：
$f(n) = \begin{cases} d & \text{若 } n=1 \\a f(n/c) + b n^x & \text{若 } n \ge 2 \end{cases}$
其解分为两种情况

若 $a = c^x$ $f(n) = b n^x \log_c n + d n^x$

若 $a \neq c^x$ $f(n) = \left( d + \frac{bc^x}{a - c^x} \right) n^{\log_c a} - \left( \frac{bc^x}{a - c^x} \right) n^x$

考虑合并排序的最大和最小比较次数

最小比较次数：每次比较后都有元素加入结果，且其中一个子数组先耗尽，仅需 $n/2$ 次比较。 $C(n) = \begin{cases} 0 & \text{若 } n=1 \\ 2C(n/2) + n/2 & \text{若 } n \ge 2 \end{cases}$

有$a=2, c=2, x=1$，故 $a = c^x$ ($2=2^1$)，解为 $C(n) \approx (n \log n) / 2$

最大比较次数：两子数组元素交替加入，需 $n-1$ 次比较。 $C(n) = \begin{cases} 0 & \text{若 } n=1 \\ 2C(n/2) + n - 1 & \text{若 } n \ge 2 \end{cases}$

最后考虑-1的问题，易得 $C(n) = n \log n - n + 1$

考虑任意正整数 n 的情况 $C(n) = \begin{cases} 0 & \text{若 } n=1 \\ C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil) + bn & \text{若 } n \ge 2 \end{cases}$

根据通用公式，可知b只会影响$nlogn$前的常数，得到：

$C(n) = \Theta(n \log n)$

寻找第 k 小元素 (Finding the k-th Smallest Element)

输入：$n$ 个元素的数组 $A[1 \dots n]$ 和整数 $k$ ($1 \le k \le n$)。
输出：$A$ 中的第 $k$ 小元素。

Algorithm SELECT (A, low, high, k)
p ← high – low + 1
if p < 44 then
    sort A  //If it is smaller than this value, it is better to sort directly; we will prove this later.
    return (A[k])
end if
q ← ⌊p / 5⌋
Divide A into q groups, with each group containng 5 elements. If 5 does not divide p evenly, the remaining elements are excluded.
Sort each of the $q$ groups individually and find their respective medians. Let the set of all these medians be $M$.
mm ← SELECT(M, 1, q, ⌈q / 2⌉)  // mm is the median of the set of all these medians

// divide A into 3 groups
A1 = {a | a < mm}
A2 = {a | a = mm}
A3 = {a | a > mm}

case
    |A1| ≥ k:// number of elements, cardinality
        return SELECT(A1, 1, |A1|, k)
    |A1| + |A2| ≥ k:
        return mm
    |A1| + |A2| < k:
        return SELECT(A3, 1, |A3|, k - |A1| - |A2|)
end case

例如：输入：数组 $A$ 包含 26 个元素，寻找 $k=13$（第 13 小）。

序列：8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 23, 7

分组：将前 25 个元素分为 5 组（排除最后的 7）。

组内排序并取中项

(8, 17, 33, 51, 57) $\to$ 33
(11, 25, 35, 37, 49) $\to$ 35
(2, 3, 13, 14, 52) $\to$ 13
(6, 12, 29, 32, 54) $\to$ 29
(5, 16, 22, 23, 23) $\to$ 22

中项集 M：{33, 35, 13, 29, 22}，递归调用找出 $M$ 的中项 $mm = 29$。

划分：

$A_1 (<29)$：{8, 17, 11, 25, 14, 3, 2, 13, 12, 6, 5, 16, 22, 23, 7} (15个)
$A_2 (=29)$：{29}
$A_3 (>29)$：{32, 51, 57, 49, 35, 37, 52, 32, 54}

判断：$k=13$。因为 $13 \le |A_1| (15)$，所以在 $A_1$ 中继续寻找。

…

这种算法可以达到常数时间复杂度。

2.1.2 划分算法

low in position划分

算法根据一个基准值（Pivot，即代码中的 $x$）将数组划分为两部分：

左半部分：所有小于或等于 $x$ 的元素。
右半部分：所有大于 $x$ 的元素。
中间：也就是 $x$ 本身，算法结束时，它会被放置在它在有序数组中最终应当所在的正确位置（归位）。

Algorithm SPLIT (A, low, high)
    i ← low
    x ← A[low]
    for j ← low + 1 to high
        if A[j] ≤ x then
            i ← i + 1
            if i ≠ j then 
                swap A[i] and A[j]
            end if
        end if
    end for
    swap A[low] and A[i]
    w ← i
    return A and w

简单来说，算法记录了小于某个值（A[low]）的元素数，并将这些元素交换到元素数的位置之前。复杂度是n-1次元素比较。

快速排序 (quicksort)

Algorithm QUICKSORT (A, low, high)
    if low < high then
        SPLIT (A, low, high, w)  // w is the new position of A[low]
        QUICKSORT (A, low, w - 1)
        QUICKSORT (A, w + 1, high)
    end if

一目了然。

考虑最坏情况时间复杂度，即数组已经有序的情况下，每次划分都需要L-1次比较，其中L为这次划分的数组的长度。因此时间复杂度为：

$T(n) = (n-1) + (n-2) + (n-3) + \dots + 2 + 1 = \frac{(n-1) \cdot n}{2} = \frac{n^2 - n}{2} = \Theta(n^2)$

考虑平均时间复杂度，实际上这里描述的是理想平衡下的情况，假设每次Split都能把数组完美的一分为二。

$T(n) = 2T(n/2) + n-1$

根据之前给出的通用公式，即可得到

$T_{average} = \Theta(n \lg n)$

2.1.3 其他分治算法的例子

各种类型的乘法

设 $u$ 和 $v$ 是两个 $n$ 位的整数（二进制），传统的乘法算法需要 $\Theta(n^2)$ 数字相乘来计算 $u$ 和 $v$ 的乘积。

把每个整数分为两部分，每部分为 $n/2$ 位，则 $u$ 和 $v$ 可重写为 $u = w2^{n/2} + x$ 和 $v = y2^{n/2} + z$。

基本分治法

$uv = (w2^{n/2} + x)(y2^{n/2} + z) = wy2^n + (wz + xy)2^{n/2} + xz$

用 $2^n$ 做乘法运算相当于简单地左移 $n$ 位，它需要 $\theta(n)$ 时间。

注意到在这个公式中，有 4次乘法运算和 3次加法运算，这蕴含着以下递推式成立：

$T(n) = 4T(n/2) + bn \quad (n > 1)$
$T(n) = d \quad (n = 1)$

这里需要用到$a\ne c^x$的情况，$T(n) = (d+b)n^2-bn = O(n^2)$

改进的分治法

对于$wz + xy$，考虑使用以下公式替代

$wz + xy = (w + x)(y + z) - wy - xz$

由此有：

$uv = wy2^n + ((w + x)(y + z) - wy - xz)2^{n/2} + xz$

这样 $u$ 和 $v$ 的乘法运算简化为 3次 $n/2$ 规模整数的乘法运算和 6次加法运算

得到递推式

$T(n) = 3T(n/2) + bn \quad (n > 1)$
$T(n) = d \quad (n = 1)$

依旧是使用$a\ne c^x$的情况，得到

$T(n) = \Theta(n^{\log_2 3}) = O(n^{1.59})$

矩阵的乘法

$A$ 和 $B$ 是两个 $n \times n$ 的矩阵，我们希望计算它们的乘积 $C = AB$。

传统算法中，

$C(i, j) = \sum_{k=1}^{n} A(i, k)B(k, j)$

算法需要 $n^3$ 次乘法运算和 $n^3 - n^2$ 次加法运算，导致其时间复杂性为 $\Theta(n^3)$。

分治算法

设 $A = \begin{pmatrix} a{11} & a{12} \ a{21} & a{22} \end{pmatrix}$ 和 $B = \begin{pmatrix} b{11} & b{12} \ b{21} & b{22} \end{pmatrix}$
计算 $C = \begin{pmatrix} c{11} & c{12} \ c{21} & c{22} \end{pmatrix}$

在此不再展开书写，其递推关系式为

$T(n) = 8T(n/2) + 4(n/2)^2 a$$$$T(n) = mn^3 + an^3 - an^2$

结果同传统方法。

STRASSEN 算法

与之前的改进相同，希望通过增加加减法来减少乘除法

具体来说

$d_1 = (a_{11} + a_{22})(b_{11} + b_{22})$
$d_2 = (a_{21} + a_{22})b_{11}$
$d_3 = a_{11}(b_{12} - b_{22})$
$d_4 = a_{22}(b_{21} - b_{11})$
$d_5 = (a_{11} + a_{12})b_{22}$
$d_6 = (a_{21} - a_{11})(b_{11} + b_{12})$
$d_7 = (a_{12} - a_{22})(b_{21} + b_{22})$

然后计算C

$c_{11} = d_1 + d_4 - d_5 + d_7$
$c_{12} = d_3 + d_5$
$c_{21} = d_2 + d_4$
$c_{22} = d_1 + d_3 - d_2 + d_6$

这种算法的时间复杂度为 $\Theta(n^{\log_2 7}) = O(n^{2.81})$。

与几何相关的算法

最近点对问题

算法旨在寻找二维平面上一组点中，距离最近的两个点。如果使用蛮力法（Brute Force）计算所有点对的距离，复杂度为 $O(n^2)$

分解：将所有点按照 $x$ 坐标排序。在中间画一条垂直线 $x = m$，将点集分为左右两个子集 $S_L$ 和 $S_R$，每个包含 $n/2$ 个点。

解决：递归地在 $S_L$ 中寻找最近距离 $\delta_L$。递归地在 $S_R$ 中寻找最近距离 $\delta_R$。令 $\delta = \min(\delta_L, \delta_R)$。此时，$\delta$ 是左右两边内部的最小距离。

合并：只需要检查分界线两侧距离不超过 $\delta$ 的“带状区域”内的点。对于带状区域内的点，按 $y$ 坐标排序。对于每个点，只需检查它上方（或下方）紧邻的若干（7）个点。

这种算法的时间复杂度：

$T(n) = 2T(n/2) + O(n) \implies T(n) = \Theta(n \log n)$

鸽巢原理：为什么检查周围的7个点
假设目前的最小距离是 $\delta$，我们在分界线 $x=m$ 左右各画出一条宽为 $\delta$ 的线，形成一个宽为 $2\delta$ 的带状区域（Strip）。我们取带状区域内的一个点 $P$，只想知道：有没有另一个点 $Q$，使得 $P$ 和 $Q$ 的距离小于 $\delta$
为了找到这样的 $Q$，它必须落在以 $P$ 为底边中心、宽为 $2\delta$、高为 $\delta$ 的矩形区域内（只用检查一边，防止重复）。
在这个 $2\delta \times \delta$ 的矩形里，最多能塞进几个点？
为了回答这个问题，我们将这个大矩形划分成 8 个小正方形，每个小正方形的边长为 $\frac{\delta}{2}$。
此时，每个小正方形的对角线长度是 $\sqrt{(\frac{\delta}{2})^2 + (\frac{\delta}{2})^2} = \frac{\delta}{\sqrt{2}} \approx 0.707\delta$。这意味着，一个小正方形内最多只能有 1 个点。
既然一共有 8 个小格子，且每个格子里最多只能有 1 个点。
那么，在这个 $2\delta \times \delta$ 的矩形区域内，最多只能存在 8 个点，在这 8 个点中，有一个点是 $P$ 自己。
除去 $P$ 自己，矩形内最多只剩下 7 个其他的点。

凸包问题

凸包问题的目标是找到一个最小的凸多边形，使得点集中的所有点都包含在多边形内部或边界上。算法包括蛮力法和快包法（QuickHull）。

蛮力法：对于集中的每一对点 $(p_i, p_j)$，判断其余所有 $n-2$ 个点是否都在这两个点连线的同一侧。如果是，则 $(p_i, p_j)$ 是凸包的一条边。

这种算法点对组合数：$C(n, 2) = \frac{n(n-1)}{2} \approx O(n^2)$。每次检查需要遍历其余 $n-2$ 个点，即 $O(n)$。总复杂度：$O(n^2) \times O(n) = \Theta(n^3)$。

快包法：找到 $x$ 坐标最小的点 $A$ 和最大的点 $B$。这两个点一定在凸包上。连接 $AB$，将点集分为“上包”和“下包”两部分。

对于线段 $AB$ 一侧的点集，找到距离直线 $AB$ 最远的点 $P$。点 $P$ 必在凸包上。显然，三角形 $\triangle ABP$ 内部的所有点都不可能是凸包顶点，直接丢弃（这一步极大减少了计算量）。将问题分解为两个子问题：处理线段 $AP$ 外侧的点，和线段 $PB$ 外侧的点。

平均情况 (Average)：每次能丢弃大量内部点，类似快速排序的平衡划分。效率为 $\Theta(n \log n)$。

最坏情况 (Worst)：如果所有点都在凸包上（例如点分布在一个圆周上），每次递归只能找出一个点，无法丢弃任何点。效率退化为 $\Theta(n^2)$。

2.2 减治法

减治技术利用了一种关系：一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，我们既可以递归地，也可以非递归地来运用减治技术。

换句话说，相比于分治法递归式中常常出现的$f(n) = af(n/c)+bn^x$这种形式，减治法的递归式常为：

$f(n) = f(n-1) * a \quad (n > 1)$
$a^n = (a^{n/2})^2 \quad (n \text{ 是偶数})$$$$a^n = (a^{(n-1)/2})^2 * a \quad (n \text{ 是大于 1 的奇数})$
$\text{gcd}(m, n) = \text{gcd}(n, m \bmod n)$

这种形式。

首先来关注前两组递归式，第一种被称作减去一个常量的减治法。即$f(n) = a^n$可以用递归定义来计算，如此，每次减治规模减少1。第二种常被称作减去一个常数因子，在实例中，常数因子等于2，也就是$a^n = (a^{n/2})^2$，每次计算规模减半。注意，规模减半不同于分治法对两个规模为 $n/2$ 的指数问题实例分别求解。

然后关注欧几里得算法，其伪代码如下：

Algorithm Euclid (m, n)
While n ≠ 0 do
    r ← m mod n
    m ← n
    n ← r
end While
return m

此算法中，$m$ 和 $n$ 既不是以常数，也不是以常数因子的方式减小。称为减去的规模是可变的。

2.2.1 减一算法示例

插入排序

考虑较小数组 $A[0 \dots n-2]$ 排序的问题已经解决了，我们得到了一个大小为 $n-1$ 的有序数组：$A[0] \le \dots \le A[n-2]$。考虑$A[n-1]$，显然，应为 $A[n-1]$ 找到一个合适的位置，并插入。

Algorithm InsertionSort(A[0…n-1])

for i ← 1 to n-1 do
w ← A[i]
j ← i-1
While j ≥ 0 and A[j] > w do
A[j+1] ← A[j]
j ← j-1
end While
A[j+1] ← w
end for

最坏情况下入是一个严格递减的数组。对于这种输入的键值比较次数是：

$C_{worst}(n) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} \in \Theta(n^2)$

最佳情况：

$C_{best}(n) = \sum_{i=1}^{n-1} 1 = n-1 \in \Theta(n)$

平均情况下，对于随机序列的数组，插入排序的平均比较次数是降序数组的一半：

$C_{avg} \approx \frac{n^2}{4}$

一般不会完全应用这种$O(n^2)$的排序算法，但可以与快排结合，但子数组规模小于某些预定的值时，直接使用插入排序停止迭代。另外，既然提到了快排，也很容易发现快排本身可以是做插入排序的改进，区别在于快排利用了比较中获得的相对大小信息，实现了划分。

拓扑排序-例

考虑五门必修课的一个集合 ${C_1, C_2, C_3, C_4, C_5}$，一个在职的学生必须在某个阶段修完这几门课程。可以按照任何次序学习这些课程，只要满足下面这些条件：

$C_1$ 和 $C_2$ 没有任何先决条件
修完 $C_1$ 和 $C_2$ 才能修 $C_3$
修完 $C_3$ 才能修 $C_4$
修完 $C_3$、$C_4$ 才能修 $C_5$
这个学生每个学期只能修一门课程

问题是学生学习顺序。

深度有限搜索

Algorithm TopologicalSort(G)
1. S ← Empty Stack
2. for each vertex u in V[G] do
3.    visited[u] ← false
4. end for
5. for each vertex u in V[G] do
6.    if visited[u] = false then
7.       DFS-Visit(u)
8.    end if
9. end for
10. return S

Algorithm DFS-Visit(u)
1. visited[u] ← true
2. for each vertex v in Adj[u] do
3.    if visited[v] = false then
4.       DFS-Visit(v)
5.    end if
6. end for
7. Push u onto S      // 当 u 成为死端（处理完所有后继）时入栈

简单来说就是将最深的节点先入栈，最浅的节点后入栈。

减治技术

Algorithm TopologicalSort(G)
1. Q <- Empty Queue
2. n <- number of vertex in G
3. while V[G] is not empty do
4.      C <- SearchSource(G)
5.      Push C into Q
6.      Remove C and all edge connected to C in G
7. end while

简单来说就是先将所有叶节点加入队列，移除与叶节点相连的边，再重复这个步骤。

生成排列

目的是生成 ${1, \dots, n}$ 的所有 $n!$ 个排列的问题。应用减治的思想，容易想到要生成 ${1, \dots, n-1}$ 的所有 $(n-1)!$ 个排列，然后把 $n$ 插入到 $n-1$ 个元素的每一种排列中的 $n$ 个可能位置中去，来得到较大规模问题的一个解。并且它们的总数量应该是 $n(n-1)! = n!$。这样，我们得到了 ${1, \dots, n}$ 的所有排列。

我们直接来看Johnson-Trotter算法。这种算法给一个排列中的每个分量 $k$ 赋予一个方向，如果分量 $k$ 的箭头指向一个相邻的较小元素，我们说它在这个以箭头标记的排列中是可移动的。

Algorithm JohnsonTrotter(n)
// 输入：一个正整数 n
// 输出：{1, …, n} 的所有排列的列表

将第一个排列初始化为 <1 <2 … <n
While 存在可移动整数 do
求最大的可移动整数 k
把 k 和它箭头指向的相邻整数互换
调转所有大于 k 的整数的方向
输出排列
end While

忽略最大的元素 $n$，剩下的元素 $1, \dots, n-1$ 也在按照 Johnson-Trotter 的规则缓慢变化。最大的元素 $n$ 是最活跃的。它在一个固定的 $n-1$ 排列中，从一端移到另一端。当 $n$ 移到底（碰到边界或更大的元素）时，$n$ 暂时“动不了”了。此时，必须轮到 $n-1$ 这个层级里的某个数动一下（生成 $n-1$ 的下一个排列）。一旦 $n-1$ 变了，$n$ 就调转方向，在这个新的排列里再次穿梭。

阶段一：子问题状态为 1 2 此时，算法让 3 在 1 2 的缝隙中从右向左穿梭。

1 2 3
1 3 2
3 1 2 (此时忽略 3，背景一直是 1 2)

阶段一的终止：3 撞到了最左边的墙，动不了了。算法去寻找下一个最大的可移动数——是 2。 2 和 1 交换，子问题从 1 2 变成了 2 1。同时，3 调头。

阶段二：子问题状态为 2 1 此时，算法让 3 在 2 1 的缝隙中从左向右穿梭。

所以这个算法尽管看起来不怎么减治，但是还是有一点减治的思想在里边的。

这种算法的时间复杂度是$\Theta(n!)$，已经达到最优。

2.2.2 减常因子示例

假币问题

给定 $n$ 枚硬币，其中一枚是较轻的假币。我们的目标是用最少的称量次数找到它。

将硬币分为三堆 $A, B, C$，每堆数量约为 $n/3$。将 $A$ 和 $B$ 放在天平两端。

情况 1 (平衡)：假币在 $C$ 堆中。
情况 2 (A 轻)：假币在 $A$ 堆中。
情况 3 (B 轻)：假币在 $B$ 堆中。

此时的递推式$W(n) = W(n/3) + 1$。每次减少至之前规模的1/3

复杂度是$\log_3 n$。

Algorithm FakeCoin(S)
1. n ← |S|  // 获取硬币数量
2. if n = 1 then
3.    return S[1]  // 基本情况：只剩一枚，它就是假币
4. end if
5. 将 S 分为三个集合 A, B, C
6. if weight(A) = weight(B) then
7.    return FakeCoin(C)
8. else if weight(A) < weight(B) then
9.    return FakeCoin(A)
10. else
11.   return FakeCoin(B)
12. end if

俄式乘法

要计算 $n \times m$。不断将 $n$ 减半（Decrease by factor 2），同时将 $m$ 加倍。

具体来说，

如果 $n$ 是偶数，则 $n \times m = (n/2) \times 2m$。
如果 $n$ 是奇数，则 $n \times m = ((n-1)/2) \times 2m + m$
当 $n=1$ 时，结束

Algorithm RussianPeasant(n, m)
1. result ← 0
2. While n > 0 do
3.    if n is odd then
4.       result ← result + m
5.    end if
6.    n ← floor(n / 2)
7.    m ← m * 2 
8. end While
9. return result

这种算法实际上就是将n转化为二进制：例如26*1：

$26 = 11010_2 = 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0$

奇数累加的部分就是二进制位为1的项。

2.2.3 减可变规模示例

插值查找

二分查找盲目地选择中间点（总是假设目标在 $1/2$ 处）。而插值查找则试图根据目标值 $v$ 在整个取值范围中的相对位置来猜测其索引。

位置 $x$ 的计算公式实际上是一个线性插值方程：

$x = l + \left\lfloor \underbrace{\frac{v - A[l]}{A[r] - A[l]}}_{\text{数值占比}} \times \underbrace{(r - l)}_{\text{索引范围}} \right\rfloor$

$\frac{v - A[l]}{A[r] - A[l]}$：计算目标值 $v$ 在当前数值范围（最小值 $A[l]$ 到最大值 $A[r]$）中处于什么比例位置
$(r - l)$：当前搜索范围的长度。
$l + \dots$：将计算出的偏移量加到起始索引上。

通常这种方法在数据分布均匀时效率较高

二叉查找树

这种方法的可变体现在二叉高度不一定相等

Algorithm BSTSearch(root, v)
1. if root = NULL then
2.    return NULL
3. end if
4. if v = root.value then
5.    return root
6. else if v < root.value then
7.    return BSTSearch(root.left, v)
8. else
9.    return BSTSearch(root.right, v)
10. end if

2.3 变治法

变治思想有 3 种主要类型：

实例化简：变换为同样问题的一个更简单或者更方便的实例。
改变表现：变换为同样实例的不同表现。
问题规约：变换为另一个问题的实例，这种问题的算法是已知的。

2.3.1 实例化简

预排序

最常见的实例化简方法是预排序，如果列表是有序的，许多问题更容易求解。

如检验数组中元素的惟一性，先对数组排序，然后只检查它的连续元素：如果该数组有相等的元素，则一定有一对元素是相互紧挨着的，反之亦然。

Algorithm PresortElementUniqueness(A[1..n])
1. sort A
2. for i ← 1 to n-1 do
3.    if A[i] = A[i+1] return false
4. end for
5. return true

可以将算法复杂度降低至 $T(n) = T_{sort}(n) + T_{scan}(n) \in \Theta(n \log n) + \Theta(n) = \Theta(n \log n)$

高斯消去法

高斯消去法的思路是把 $n$ 个线性方程构成的 $n$ 元联立方程组变换为一个等价的方程组。

最简单的做法是模拟手算的过程：

Algorithm GaussElimination(A[1..n, 1..n], b[1..n])
1. for i ← 1 to n do A[i, n+1] ← b[i] // 扩展该矩阵
2. for i ← 1 to n-1 do // Eliminate/Diag
3.    for j ← i+1 to n do // Row
4.       for k ← i to n+1 do // Col
5.          A[j, k] ← A[j, k] - A[i, k] * A[j, i] / A[i, i]
6.       end for
7.    end for
8. end for

两个问题：

$A[i,i] = 0$
$A[i,i]$ 可能会非常小，比例因子 $A[j,i]/A[i,i]$ 非常大，以至于 $A[j,k]$ 的新值会因为舍入而严重失真

解决办法：

每次都去找第 $i$ 列系数的绝对值最大的行，然后把它作为第 $i$ 次迭代的基点。
保证比例因子的绝对值永远不会大于 1。

Algorithm BetterGaussElimination(A[1..n, 1..n], b[1..n])
1.  for i ← 1 to n do A[i, n+1] ← b[i]
2.  for i ← 1 to n-1 do
3.     pivotrow ← i
4.     for j ← i+1 to n do // E(col)
5.        if |A[j, i]| > |A[pivotrow, i]| then pivotrow ← j
6.     end for
7.     for k ← i to n+1 do // Row
8.        swap(A[i, k], A[pivotrow, k])
9.     end for
10.    for j ← i+1 to n do
11.       temp ← A[j, i] / A[i, i]
12.       for k ← i to n+1 do // Row
13.          A[j, k] ← A[j, k] - A[i, k] * temp
14.       end for
15.    end for
16. end for

LU分解
为了解这个方程，设

L：由主对角线上的 1 和在高斯消去过程中，行的乘数所构成的下三角矩阵
U：高斯消去过程后的上三角矩阵
求解过程：
设 $y=Ux$，则 $Ly=b$
解 $Ly=b$，得 $y$
再解 $Ux=y$，得到 $x$

AVL树

AVL树是一个要求树每个节点的左右子树的高度差不能超过 1的二叉查找树（BST），因此也包括红黑树、分裂树等数据结构。因此，可被视作一种实例化简的示例。

理论上，所有包含 $n$ 个节点的 AVL 树的高度 $h$ 都满足这个不等式

$\lfloor \log_2 n \rfloor \le h < 1.4405 \log_2(n+2) - 1.3277$

在平均情况下，查找一棵 AVL 树需要的比较次数和用折半查找 (Binary Search) 查找一个有序数组是几乎相同的。

2.3.2 改变表现

2-3树

除了avl树，另一种思路是允许一个节点不止包含一个键，也就是改变BST的表现。
2-3 树是一种可以包含两种类型节点的树：2 节点、3 节点

2 节点：只包含一个键 $K$ 和两个子女（子节点）：左子节点作为一棵所有键都小于 $K$ 的子树的根。右子节点作为一棵所有键都大于 $K$ 的子树的根。
3 节点：包含两个有序的键 $K_1$ 和 $K_2$ ($K_1 < K_2$) 并且有 3 个子节点：最左边的子节点作为键值小于 $K_1$ 的子树的根。中间的子节点作为键值位于 $K_1$ 和 $K_2$ 之间的子树的根。最右边的子节点作为键值大于 $K_2$ 的子树的根。
树中的所有叶子必须位于同一层

查找和插入

查找不难理解

Algorithm TwoThreeSearch(node, key)
// 输入：当前节点 node，目标键 key
// 输出：找到的节点或 NULL

1. if node = NULL then return NULL

// Case 1: 节点是 2-node (只有 k1)
2. if node is 2-node then
3.    if key = node.k1 then return node
4.    else if key < node.k1 then return TwoThreeSearch(node.left, key)
5.    else return TwoThreeSearch(node.right, key)

// Case 2: 节点是 3-node (有 k1, k2)
6. else 
7.    if key = node.k1 or key = node.k2 then return node
8.    else if key < node.k1 then return TwoThreeSearch(node.left, key)
9.    else if key > node.k2 then return TwoThreeSearch(node.right, key)
10.   else return TwoThreeSearch(node.middle, key) // k1 < key < k2
11. end if

插入涉及到节点分裂和向上提升，可以参见之后的例子

Algorithm TwoThreeInsert(root, key)
1. (promoted_key, new_node) ← Put(root, key)
2. if promoted_key ≠ NULL then
      // 根节点分裂了，创建新的根 (树高 +1)
3.    new_root ← New Node(promoted_key)
4.    new_root.left ← root
5.    new_root.right ← new_node
6.    root ← new_root
7. end if

Algorithm Put(node, key)
// 返回值：(提升的键, 新分裂出的右兄弟节点)
// 如果没有分裂，返回 (NULL, NULL)

1. if node is Leaf then
      // 
---
 叶子节点处理 
---

2.    if node has 1 key then
3.        Add key to node (sort keys), return (NULL, NULL)
4.    else // node has 2 keys (Overflow!)
5.        return SplitNode(node, key, NULL, NULL)
6.    end if

   // 
---
 内部节点递归 
---

7. else 
8.    child ← find correct child for key (left, middle, or right)
9.    (p_key, p_node) ← Put(child, key) // 递归向下

10.   if p_key = NULL then return (NULL, NULL) // 子节点没分裂，结束
      
      // 子节点分裂了，当前节点需要接纳提升上来的 p_key
11.   if node has 1 key then
          // 当前是 2-node，变成 3-node，容纳 p_key 和 p_node
12.       Absorb(node, p_key, p_node) 
13.       return (NULL, NULL)
14.   else
          // 当前是 3-node，再次发生溢出，继续向上传递
15.       return SplitNode(node, p_key, p_node)
16.   end if
17. end if

Algorithm SplitNode(node, new_key, new_child)
// 将 3 个键 (原来的两个 + 新插入的) 排序为 s, m, l
// m (中间键) 被提升，s 留要在原节点，l 放到新节点
1. small, middle, large ← Sort(node.k1, node.k2, new_key)
2. node.keys ← {small} // 原节点只保留最小的
3. new_sibling ← New Node(large) // 新节点存放最大的
4. Handle children reassignment for internal nodes...
5. return (middle, new_sibling)

例如，为列表 9, 5, 8, 3, 2, 4, 7 构造一棵 2-3 树。

插入 9；树为空，创建根；[9]
插入 5；5 < 9，根是 2-node，直接放入；[5, 9]
插入 8；第一次分裂，最小 5 留在左边，最大 9 去新右节点，中间 8 提升成为新根；[5]<-[8]->[9]
插入 3；3 < 8，进入左子树 [5]，[5] 是 2-node，直接变为 [3, 5]；[3,5]<-[8]->[9]
插入 2；第二次分裂，最小 2 留左，最大 5 去右，中间 3 提升，父节点 [8] 是 2-node，容纳 3 变为 [3, 8]
1
2
3
[3, 8]
/ | \
[2] [5] [9]
插入4；
1
2
3
[3, 8]
/ | \
[2] [4,5] [9]
插入 7；
- 7 在 3 和 8 之间，进入中间子树 [4, 5]溢出，4 留，7 去新右，中间 5 提升;
- 父节点是 [3, 8]溢出，最小 3 留左，最大 8 去右，中间 5 继续提升，5 成为新的根节点
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  [3, 8]
  / | \
  [2] [4,5,7] [9]
  ↓
  [3, 5, 8]
  / | | \
  [2] [4] [7] [9]
  ↓
  [5]
  / \
  [3] [8]
  / | | \
  [2] [4] [7] [9]

一个具有最少节点的高度为 $h$ 的 2-3 树是一颗全部由 2 节点构成的满树

对于任何包含 $n$ 个节点、高度为 $h$ 的 2-3 树，有

$n \ge 1 + 2 + \dots + 2^h = 2^{h+1} - 1$

一个具有最多节点的高度为 $h$ 的 2-3 树是一棵全部由 3 节点构成的满树，每个节点都包含两个键和三个子女

对于任何 $n$ 个节点的 2-3 树，有

$n \le 2 \cdot 1 + 2 \cdot 3 + \dots + 2 \cdot 3^h = 2(1 + 3 + \dots + 3^h) = 3^{h+1} - 1$

故有

$\log_3(n+1) - 1 \le h \le \log_2(n+1) - 1$

无论在最差情况还是在平均情况，2-3树的查找、插入和删除的时间效率都属于 $\Theta(\log n)$

堆排序

在上一章我们应用的堆重组数组的形式现实也是一种改变表现，再次不再赘述

霍纳法

对于多项式 $p(x) = 2x^4 - x^3 + 3x^2 + x - 5$，有：

$\begin{aligned} & p(x)=2 x^4-x^3+3 x^2+x-5 \\ & =x\left(2 x^3-x^2+3 x+1\right)-5 \\ & =x\left(x\left(2 x^2-x+3\right)+1\right)-5 \\ & =x(x(x(2 x-1)+3)+1)-5 \end{aligned}$

表格计算法使用一个两行的表来帮助计算，第一行包含了该多项式的系数；第二行中，除了第一个单元用来存储 $a_n$，其他单元都用来存储中间结果。用第二行的最后一个单元乘以 $x$ 的值再加上第一行的下一个系数，来算出表格下一个单元的值。以这种方式算出的最后一个单元的值，就是该多项式的值。

$\begin{array}{llllll} \text { 系数 } & 2 & -1 & 3 & 1 & -5 \\ \mathbf{X = 3} & 2 & 3 * 2+(-1)=5 & 3 * 5+3=18 & 3 * 18+1=55 & 3 * 55-5=160 \end{array}$

但是这种方法在计算$a^n$ 时，退化成了一种对 $a$ 自乘的蛮力算法，以及一些无用的加法。

有两种基于改变表现 (Representation Change) 思想的计算 $a^n$ 的算法

设 $n = b_I \dots b_i \dots b_0$ 是在二进制系统中表示一个正整数 $n$ 的比特串，则可以通过以下多项式的值来计算 $n$：

$p(x) = b_I x^I + \dots + b_i x^i + \dots + b_0$

其中， $x=2$，可以应用霍纳法计算。

p ← 1  
for i ← I-1 downto 0 do
    p ← 2*p + b_i
end for

其中每一步都需要计算$2*p + b_i$

由于 $a^n = a^{p(2)}$，有

$a^{2p + b_i} = a^{2p} \cdot a^{b_i} = (a^p)^2 \cdot a^{b_i}$

即可替代上述伪代码中的$p ← 2*p + b_i$一步。

从左至右二进制幂算法

Algorithm LeftRightBinaryExponentiation(a, b(n))
// 用从左至右二进制幂算法计算 a^n
1. product ← a
2. for i ← I-1 downto 0 do
3.    product ← product * product
4.    if b_i = 1 then 
5.       product ← product * a
6.    end if
7. end for
8. return product

2.3.3 问题规约

即使用已解问题解决未解问题

比如使用最小公倍数和最大公因数的乘积等于两个数本身的成绩，用求解最大公因数的方法求解最小公倍数

规约为线性规划问题

线性规划问题是一个多变量线性函数的最优化问题，这些变量所要满足的一些约束是以线性等式或线性不等式的形式出现的。

标准形式：

$\begin{aligned} &\text { opt } z=c_1 x_1+\cdots+c_n x_n\\ &\text { s.t. } \quad a_{11} x_1+\cdots+a_{1 n} x_n \leq b_1\\ &\text { ⋯ }\\ &a_{m 1} x_1+\cdots+a_{m n} x_n \leq b_m \end{aligned}$

背包问题

背包问题的连续版本按照线性规划规约：

$\begin{gathered} \max \sum_{j=1}^n v_j x_j \\ \text { s.t. } \quad \sum_{j=1}^n w_j x_j \leq W \\ 0 \leq x_j \leq 1, \quad j=1, \ldots, n \end{gathered}$

我们会在动态规划的部分讨论离散情况（或许吧）