--- tags: - 算法分析与设计 - 分治 - 递归 abstract: 递归、分治、归并排序与快速排序 finished: false 上一篇: - - 计算机系/算法分析与设计/03 运行时间与渐进分析|上一篇 下一篇: - - 计算机系/算法分析与设计/05 复杂度分析专题|下一篇 返回目录: - - 计算机系/算法分析与设计/算法分析|算法分析与设计学习指南 前置知识: - - 计算机系/算法分析与设计/03 运行时间与渐进分析|前置知识 --- # 递归式 递归算法采用一种分而治之的方式，把一个大问题分解为若干个相似的小问题 关键时根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度 递归式就是一个等式，它通过通常更小的函数参数值来描述一个函数。 # 递归算法 在定义一个过程或函数时出现调用本过程或者本函数的成分，称之为递归 若调用自身，称之为直接递归。若过程或函数p调用过程或函数q而q又调用p，称之为间接递归 任何间接递归都可以等价地转换为直接递归 如果一个递归过程或递归函数中递归调用语句时最后一句执行语句，则称这种递归调用为尾递归 ``` int fun(int n) { if(n==1) return (1); else return (fun(n-1)*n); } ``` 直接调用fun(n-1),所以一个直接递归函数，且是最后一条语句，又属于尾递归。 能够用递归的方法应该满足以下条件： 1、 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。 2、 递归调用次数必须是有限的（必须有一个明确的递归结束条件，或称为递归出口，否则将无限进行下去） 3、 必须有结束递归的条件来中止 缺点：运行效率较低，堆栈溢出 什么时候使用递归？ 1、 定义是递归地，如n！或斐波那契数列 2、 数据结构是递归的，如链表 3、 求解的方法是递归的 **（1）** 能够分析算法时间复杂度；能够求解递归式。 **汉诺塔问题** 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上。递归分解的过程是： $$ Hanoi(n-1,x,z,y);\\ move(n,x,z);\text {将第n个圆盘从x移到z} \\ Hanoi(n-1,y,x,z); $$ 大问题转化为若干个小问题求解 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。 求n! 的算法对应递归模型： $$\left\{ \begin{array}{lr} fun\left( 1 \right) =1, & \left( 1 \right)\\ fun\left( n \right) =n*fun\left( n-1 \right) & n>1 \left( 2 \right)\\ \end{array} \right. $$ (1)给出递归的终止条件。 （2）给出fun(n)与fun(n-1)之间的关系，前者称为递归出口，后者称为递归体。 一个递归模型是由递归出口和递归体两部分组成、 递归出口的一般格式如下：f(s1)=m1 递归体的一般格式如下： $f(s_n+1)=g(f(s_i),f(s_{i+1}),...,f(s_n),c_j,c_{j+1},...,c_m)$ $s_{n+1}$是递归的“大问题”，$s_i,s_{i+1},s_n$为递归“小问题”，$c_j,c_{j+1},...,c_m$是若干个可以直接（用非递归）解决的问题，g是一个非递归函数，可以直接求值 S1与m1均为常量，有些递归问题可能有几个递归出口 递归算法的执行过程 递归程序虽然每次调用的是相同的子程序，但是它的参量、输入数据等均有变化 随着调用的不断深入，必定会出现调用到某一层的函数时，不再执行递归调用而种植函数的执行，即遇到递归出口。 递归调用是函数嵌套调用的一种特殊情况，即它是调用自身代码 由于每次调用时，它的参量和局部变量均不同，因而保证了各个复制执行时的独立性。 系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参量值。 这些单元以系统栈的形式存放，每调用一次进栈一次。当返回时出栈，把当前栈顶保留的值送回相应的参量中进行恢复，并按栈顶中的返回地址，从断点继续执行。 每递归调用一次，就需进栈一次。最多的进栈元素个数称为递归深度。当n越大，递归深度越深，开辟的栈空间也越大。 每当遇到递归出口或完成本次执行时，需要退栈一次，并恢复参量值，当全部执行完毕，栈应为空。 递归调用分两步：1分解过程，将大问题分解成小问题，直到递归出口。2、然后进行第二步的求值。即已知小问题求大问题 对于给定的含有n个元素的数组a，分别采用简单的选择排序和冒泡排序方法对其按元素递增排序 **简单选择排序** f(a,n,i)用于对a[i...n-1]元素序列（共n-i个元素）进行简单的选择排序。是”大问题“ f(a,n,i+1)用于对a[i+1...n-1]元素序列（共n-i-1个元素）进行简单选择排序，是”小问题“ 当i=n-1时所有元素有序，算法结束。 >f(a,n,i)=不做任何事情，算法结束.当i=n-1 > >f(a,n,i)=通过简单比较挑选a[i...n-1]中的最小元素 a[k]放在a[i]处；否则f(a,n,i+1); ``` void SelectSort(int a[],int n,int i) { int j,k; if (i==n-1) return ;//满足递归出口 else { k=i; //k记录a[i...n-1]中最小元素的下标 for (j=i+1;jf(a,n,i)=不做任何事情，算法结束.当i=n-1 > >f(a,n,i)=对a[i...n-1]元素序列，从a[n-1] 开始进行相邻元素比较;否则 > >若相邻元素反序则将两者交换 > >若没有交换则返回，否则执行f(a,n,i+1); 整数划分问题：把一个正整数表示成一系列正整数之和 $$ n=n1+n2+..+n_k,n1 \ge n2 \ge ... \ge n_k \ge 1,k\ge 1$$ 正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n) p(6)=11 如果{n1,n2,..,ni}中最大加数s 不超过m，即s=max(n1,n2,...,ni)≤m 则称它属于n的一个m划分。我们记n的m划分个数为f(n,m).该问题就转化为求n的所有划分个数f(n,n) f(n,m)的递归关系 1. f(1,m)=1,m≥1 当n=1时，不论m值为多少，只有一个划分即1个1. 2. f(n,1)=1,n≥1 当m=1，不论n的值为多少，只有一种划分即n个1 3. f(n,m)=f(n,n)，m≥n 最大加数实际上不能超过n。例如f(3,5)=f(3,3) 4. f(n,n)=1+f(n,n-1) 正整数n的划分是由s=n的划分和s≤n-1的划分构成。例如，f(6,6)=1+f(6,5) 5. f(n,m)=f(n,m-1)+f(n-m,m),n＞m＞1 正整数n的最大加数s不大于m的划分，是由s=m的划分(即有一个加数已经是m了)和s≤m-1的划分组成 $$ p(n)=f(n,m) = \left\{ \begin{array}{ll} 1, &n=1,m=1 \\ f(n,n), & nm>1 \end{array} \right. $$ # 递推 递推问题求解的基本步骤 鸽巢原理也称抽屉原理，是组合数学中一个重要的原理. l 重点：递推关系式求解方法 l 难点：分治递推关系求解 即使得不到通项公式，也可以用递推公式，加上循环得到。 除了循环（递推），还可以写成递归 能不用递归就不用递归，效率慢 自上而下是递归，自下而上是递推。 递推问题 [Problem - 2050](http://acm.hdu.edu.cn/showproblem.php?pid=2050) 首先，确认能否容易得到最简单情况的解（n=1、2） 然后，假设规模为N-1的情况已经得到解决 最后。当扩大到N，求递推公式。 1. 空间换时间的思想，程序实现的时候开辟一个数组 2. 并不一定是N-1到N的分析 [Problem - 2046](http://acm.hdu.edu.cn/showproblem.php?pid=2046) 先前的递推，是根据N-1，来分析加上N的结果 这个题目时将大问题分解成小问题 首先将根据最后一列是竖着还是横着放分成两种 竖着放，那么剩下的N-1列随便排 横着放，剩下的N-2列随便排 2. 骨牌铺满方格 ![image-20251207123141995](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251207123141995.png) [Problem - 1297](http://acm.hdu.edu.cn/showproblem.php?pid=1297) 找合法的情况 1、队列尾是M,那么前面N-1是合法的，他就是合法的；如果是非法的，就是非法的。 2、队列尾是F，那么倒数第二个必须是F；那么N-2个前面的，如果合法，则合法；如果非法，也不一定；再根据两个，如果MF，则合法。因此三种情况合法。 可以推出二维的公式 $$\begin{cases} F_1\left( n \right) =F_1\left( n-2 \right) +2F_2\left( n-2 \right)\\ F_2\left( n \right) =F_1\left( n-2 \right) +F_2\left( n-2 \right) +F_2\left( n-3 \right)\\ F\left( n \right) =F_1\left( n \right) +F_2\left( n \right)\\ \end{cases}$$ 或者 $$\begin{cases} F_1\left( n \right) =F_1\left( n-1 \right) +F_2\left( n-1 \right)\\ F_2\left( n \right) =F_1\left( n-2 \right) +F_2\left( n-1 \right)\\ F\left( n \right) =F_1\left( n \right) +F_2\left( n \right)\\ \end{cases}$$ 长度为n的字符串，用HDU来，但是H后面不能接D，D后面不能接U。请问有多少种可能？ $$\begin{cases} H_n=H_{n-1}+D_{n-1}+U_{n-1}\\ D_n=D_{n-1}+U_{n-1}\\ U_n=H_{n-1}+U_{n-1}\\ \end{cases}$$ 总而言之，就是找合法的结果。非法的如何变成合法就是关键。不能有遗漏和重复。 [Problem - 2045](http://acm.hdu.edu.cn/showproblem.php?pid=2045) 同样的，如果N-1合法，那么最后一个只有一种情况。 如果N-1不合法，那么只可能是首尾不一样，那么最后一个有两种 情况 因此为F(n)=F(n-1)+2F(n-2) [Problem - 1465](http://acm.hdu.edu.cn/showproblem.php?pid=1465) 有 n封信和 n 个对应的信封，把所有信都装错信封（即没有一封信装入它对应的信封），求装法的总数 Dn（称为**错排数**）。D1=0,D2=1 考虑第 n 封信，它不能装进第 n 个信封，所以它只能放进前 n-1 个信封中的某一个，有 n−1 种选择。 当N-1封全错，任意一个和第N个交换，就构成了全错的情况， 当N-1封有对的一个，即N-2封错的，那就把那一个和第N个交换,就构成了全错 或者假设第 n 封信放进了第 k 个信封（k ≠ n），那么第 k 封信有两种情况： - 第 k 封信放进第 n 个信封 → 剩下的 n-2 封信错排，即 Dn−2种。 - 第 k 封信不放进第 n 个信封 → 相当于把第 k 封信和剩下的n-2封信看作“禁止对应”的新问题，等价于 n-1 封信的错排，即 Dn−1种。 递推公式: $D(n)=(n-1)(D_{n-1}+D_{n-2})$ 圆连线问题 圆周上按顺序标有2n个点，顺时针或者逆时针围成一个圆，将n个线段把这2n个数字连在一起，线段不交叉一共有多少种？ 固定一个点，比如1号点，它必须连到某个偶数号点。 假设1号点连到2k号点，那么圆被分成两段弧，分别有2k-2和2n-2k个点。 $C_n=\Sigma_{k=1}^n C_{k-1}C_{n-k}$ F0=1 $F_n=\Sigma_{i=0}^{n-1}F_iF_{n-1-i}$ k-1=i 优美的卷积公式 卡特兰数列 $$C_n=\frac{\left( \begin{array}{c} 2n\\ n\\ \end{array} \right)}{n+1}$$ 爬楼梯 搞定一步就可以了，走到第n层，要么n-1，要么n-2 $F1=1,F2=2,F_n=F_{n-1}+F_{n-2}$ # 分治法 l 排序算法：合并排序、快速排序、随机排序 l 寻找中项和第K小元素 l 大整数乘法 l 矩阵乘法 l 最近点对问题 基本情况：问题足够小我们可以直接解决，不需要递归 分解（divide）：将原问题分解成一些列子问题，形式与原问题一致 求解（conquer）：递归地求解各子问题，若子问题足够小，则停止递归，直接求解 归并（merge）：将子问题的解合并成原问题的解 问题特征： 1. 该问题的规模缩小到一定的程度就可以容易地解决 2. 该问题可以分解为若干个规模较小的相同问题 3. 分解出的子问题的解可以合并为该问题的解 4. 各个子问题相互独立，即子问题之间不包含公共子问题 divide-and-conquer (P) ``` { if |P|≤n0 return adhoc(P); 将P分解为较小的子问题P1,P2,..,Pk； for (i=1;i≤k;i++)//循环处理k次 yi=divide-and-conquer(Pi)//递归解决Pi return merge(y1,y2,...,yk)//合并子问题 } ``` 原问题应该分为多少个子问题才较适宜？子问题的规模应该怎样才为适当？ 这些问题很难予以肯定的回答。但用分治法设计算法时，最好使子问题的规模大致相同。 换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。 k=1，减治法；k=2，称为二分法； 分治法是问题分成多个子问题，然后最后将问题合并起来，从而求得其解。 减治法是将问题分解，但是没有将解合并，解就在子问题的解中。折半查找属于减治法。 ## 折半查找 ``` int BinSearch(int a[],int low,int high,int k) { int mid ; if (low <=high) { mid=(low+high)/2; if (a[mid]==k) return mid; if (a[mid]>k) return BInsearch(a,low,mid-1,k) else return BinSearch(a,mid+1,high,k) } else return -1; } ``` 折半查找算法的主要时间花费在元素比较上，对于含有n个元素的有序表，采用折半查找时最坏情况下的元素比较次数为C(n) > C(n)=1,当n=1 > > $C(n)\le 1+C(\lfloor n/2 \rfloor)$,当n≥2 由此得到:$C(n)\le \lfloor log_2 n \rfloor+1$ 折半查找的主要时间花在元素比较上，所以算法的时间复杂度为$O(log_2 n)$ ## 快速排序 基本思想：在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在两个子序列中间，这个过程称为划分。 对两个子序列分别重复上述过程，直至每个子序列内只有一个记录或空为止。 $a[s]..a[i-1]\ a[i] \ a[i+1] ..a[t]$ > f(a,s,t)=不做任何事情 当a[s...t]中长度小于2 > > f(a,s,t)=i=Partition(a,s,t);其他情况 > > f(a,s,i-1);f(a,i+1,t) 1. 分解：将原序列a[s...t]分解成两个子序列a[s...i-1]和a[i+1...t]，其中i为划分的基准位置 2. 求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回，否则递归地求解各个子问题 3. 合并：由于整个序列放在数组a中，排序过程是就地进行的，合并过程不需要执行任何操作 ```cpp int Partition(int a[],int s,int t) { int i=s,j=t; int tmp=a[s]; while (i!=j) { while (j>i && a[j]>=tmp) j--; a[i]=a[j]; while(i 2` 时，称为**多路归并**。通常所说的归并排序默认为二路归并。 ![image-20260301161744820](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301161744820.png) ![|601x601](https://pica.zhimg.com/v2-b4bbae0699c96e620f19f1703e32e3ea_1440w.jpg) ### 代码实现 ```cpp void MergeSort(int a[], int low, int high) { if (low < high) { int mid = (low + high) / 2; //或者int mid = (l + r) >> 1; MergeSort(a, low, mid); MergeSort(a, mid + 1, high); Merge(a, low, mid, high); } } } void Merge(int a[], int low, int mid, int high) { int i = low; int j = mid + 1; int cnt = 0; while (i <= mid && j <= high) { if (a[i] <= a[j]) tmp[cnt++] = a[i++]; else tmp[cnt++] = a[j++]; } while (i <= mid) tmp[cnt++] = a[i++]; while (j <= high) tmp[cnt++] = a[j++]; for (int k = 0; k < cnt; k++) a[low + k] = tmp[k]; } ``` ```cpp 2 int l = low, r = high; 3 int i = l, j = mid + 1, cnt = 0; 4 while (i <= mid && j <= r) 5 { 6 if (a[i] <= a[j]) 7 tmp[cnt++] = a[i++]; 8 else 9 tmp[cnt++] = a[j++]; 10 } 11 12 while (i <= mid) 13 tmp[cnt++] = a[i++]; 14 15 while (j <= r) 16 tmp[cnt++] = a[j++]; 17 18 for (int k = 0; k < cnt; k++) 19 a[low + k] = tmp[k]; ``` `tmp` 是辅助数组。比较时使用 `<=`，相等时优先取左侧元素，因此该实现是稳定排序。 ### 一次 Merge 的时间复杂度 设： - `n1 = mid - low + 1`：左半部分元素个数； - `n2 = high - mid`：右半部分元素个数； - `n = n1 + n2`：合并后的元素总数； - `t`：主 `while` 循环体执行次数； - `x`：取左数组元素的次数； - `t-x`：取右数组元素的次数。 $x+(t−x)=t$ 表示主 `while` 一共取走了 `t` 个元素。 更准确地写成： | 行号 | 代码 | 执行次数 | | --- | ------------------------------------ | -------------------- | | 2 | `int l = low, r = high;` | 1 | | 3 | `int i = l, j = mid + 1, cnt = 0;` | 1 | | 4 | `while (i <= mid && j <= r)` 条件判断 | `t + 1` | | 6 | `if (a[i] <= a[j])` 条件判断 | `t` | | 7 | 左数组分支：`tmp[cnt++] = a[i++];` | `x` | | 9 | 右数组分支：`tmp[cnt++] = a[j++];` | `t - x` | | 12 | `while (i <= mid)` 条件判断 | `(n1 - x) + 1` | | 13 | 左数组剩余复制：`tmp[cnt++] = a[i++];` | `n1 - x` | | 15 | `while (j <= r)` 条件判断 | `(n2 - (t - x)) + 1` | | 16 | 右数组剩余复制：`tmp[cnt++] = a[j++];` | `n2 - (t - x)` | | 18 | `for (int k = 0; k < cnt; k++)` 条件判断 | `n + 1` | | 19 | `a[low + k] = tmp[k];` | `n` | --- - 左右子数组一共有 $n_1 + n_2 = n$ 个元素； - 主循环最多取出 `n-1` 个元素，剩余元素由后续循环复制。 - 这些元素最终都要写回原数组； - 所以回写操作的次数恰好是 $n$（给出下界 $\Omega(n)$）； - 而扫描、比较、复制剩余等所有操作的总次数都不超过 $c \cdot n$（给出上界 $O(n)$）； - 两者夹逼，得到 $T_{merge}(n) = \Theta(n)$。 把 cost 和 times 相乘再求和： $$ \begin{aligned} T_{merge}(n) ={} & c_1 + c_2 + c_3(t+1) + c_4 t + c_5 x + c_6(t-x) \\ & + c_7\bigl((n_1-x)+1\bigr) + c_8(n_1-x) \\ & + c_9\bigl((n_2-(t-x))+1\bigr) + c_{10}\bigl(n_2-(t-x)\bigr) \\ & + c_{11}(n+1) + c_{12}n \end{aligned} $$ 整理后： $$ \begin{aligned} T_{\text{merge}} ={}&C_0 +(c_3+c_4+c_6-c_9-c_{10})t\\ &+(c_5-c_6-c_7+c_9+c_{10})x\\ &+(c_7+c_8)n_1\\ &+(c_9+c_{10})n_2\\ &+(c_{11}+c_{12})n \end{aligned} $$ 其中 $$ C_0=c_1+c_2+c_3+c_7+c_9+c_{11} $$ 更细的计数中，`t` 和 `x` 会随输入排列变化，所以不存在只由 `n` 决定的固定精确值；但这不影响渐进复杂度。 $$ 0\le t\le n-1,\qquad 0\le x\le t $$ 但无论输入如何，归并过程都必须： - 扫描左右子数组； - 复制剩余元素； - 将最终的 `n` 个元素写回原数组。 因此： $$ T_{\text{merge}}(n)=\Theta(n) $$ > [!important] 核心结论 > 单次 `Merge` 合并耗时为 `Θ(n)`。 --- 一、什么是“子问题”？ **子问题**就是：原问题规模变小后的一个实例。 在归并排序里： - **原问题**：把 `A[p..r]` 排好序。 - **分解（Divide）**：找到中点 `q`，把 `A[p..r]` 分成 `A[p..q]` 和 `A[q+1..r]`。 - **子问题**就是： - 子问题 1：把 `A[p..q]` 排好序 - 子问题 2：把 `A[q+1..r]` 排好序 这两个子问题，就是“分解”这一步产生的结果。 --- 二、求解（Conquer）是什么？ **求解（Conquer）就是去解决这些子问题。** ```text 3 MERGE-SORT(A, p, q) 4 MERGE-SORT(A, q+1, r) ``` 这两行就是“求解”步骤。 - 第 3 行：递归地求解子问题 1（排序左半部分） - 第 4 行：递归地求解子问题 2（排序右半部分） **注意**：这里的“求解”并不是说这两行写完了子问题就解决了，而是说： **通过递归调用，把子问题继续分解，直到子问题小到可以直接解决（只剩一个元素，天然有序）。** 所以，“求解”这一步在代码里体现为**递归调用**。 ---- ### 归并排序递归式 当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间，该方程根据在较小输入上的运行时间来描述在规模为 n 的问题上的总运行时间。然后，我们可以使用数学工具来求解该递归式并给出算法性能的界。 归并排序递归式整理 分治算法运行时间的递归式来自基本模式的三个步骤。 如前所述，我们假设 T(n) 是规模为 n 的一个问题的运行时间。 若问题规模足够小（即一个元素），如对某个常量 $n_{0} \gt 0,n \lt n_{0}$，则直接求解需要常量时间，我们将其写作 Θ(1)。 假设把原问题分解成 a 个子问题，每个子问题的规模是原问题的 1/b。（对归并排序，a 和 b 都为 2，然而，我们将看到在许多分治算法中，a ≠ b。） 为了求解一个规模为 n/b 的子问题，需要 T(n/b) 的时间，所以需要 aT(n/b) 的时间来求解 a 个子问题。如果分解问题成子问题需要时间 D(n)，合并子问题的解成原问题的解需要时间 C(n). 一般分治算法的递推式为： $$ T(n)= \begin{cases} \Theta(1), & n1. \end{cases} $$ $$T(n) = \begin{cases} c, & \text{if } n = 1 \\ 2T(n/2) + cn, & \text{if } n > 1 \end{cases}$$ ### 递归树 ![[guibinganimated.gif]] ![image.png|619x504](https://nas.chenalna.site/sata11-19012711369/images/20260917003525744.png) ![image.png|660x657](https://nas.chenalna.site/sata11-19012711369/images/20260923133518752.png) 以 `n=8` 为例： ```text T(8) = 2T(4) + Θ(8) = 2[2T(2) + Θ(4)] + Θ(8) = 4[2T(1) + Θ(2)] + 2Θ(4) + Θ(8) = 8T(1) + 4Θ(2) + 2Θ(4) + Θ(8) ``` 8 T(1)：8 个规模为 1 的子问题，每个常量时间。 Θ(8)：根节点这一层合并 8 个元素。 2Θ(4)：第二层两个节点，各合并 4 个元素。 4Θ(2)：第三层四个节点，各合并 2 个元素。 每一层的合并总代价都是 Θ(n) 递归树代价分析总结 - 根节点代表规模为 $n$ 的问题，代价为 $c_2n$。 - 下一层有 $2$ 个规模为 $n/2$ 的子问题，每个代价为 $c_2(n/2)$，该层总代价仍为 $c_2n$。 - 每一层的总代价都是 $c_2n$。即：顶层之下的第 $i$ 层具有 $2^i$ 个结点，每个结点贡献代价 $c_2(n/2^i)$，因此，该层具有总代价 $2^i c_2(n/2^i) = c_2n$。 - 规模从 $n$ 每次减半，直到 $1$，共有 $\lg n + 1$ 层（其中非叶节点层 $\lg n$ 层）。 - 叶节点（底层）共有 $n$ 个，每个代价为 $c_1$，叶节点总代价为 $c_1n$。 关于树高的严谨证明（归纳法） 树的层数为 $\lg n + 1$（其中 $n$ 是叶节点的数量，对应输入规模）。 - 基本情况：当 $n = 1$ 时，树只有 1 层。因为 $\lg 1 = 0$，所以 $\lg n + 1$ 给出了正确的层数。 - 归纳假设：假设具有 $2^i$ 个叶节点的递归树的层数为 $\lg 2^i + 1 = i + 1$。 - 归纳步骤：考虑输入规模为 $2^{i+1}$ 的情况。具有 $2^{i+1}$ 个叶节点的树，比具有 $2^i$ 个叶节点的树多 1 层，所以总层数为 $(i + 1) + 1 = \lg 2^{i+1} + 1$。得证。 最终总时间计算 和插入排序不同，归并排序每层合并都是线性时间；因此递归深度为 $Θ(log n)$ 要计算递归式表示的总代价，只需将各层的代价相加： - 非叶节点层代价：共有 $\lg n$ 层，每层代价为 $c_2n$，总代价为 $c_2n \lg n$。 - 叶节点层代价：只有 1 层，代价为 $c_1n$。 - 忽略低阶项和常数后，总代价公式： $$ T(n) = c_2n \lg n + c_1n = \Theta(n \lg n) $$ ### 最终复杂度 $$ T(n)=2T(n/2)+\Theta(n) $$ 由递归树或主定理： $$ \boxed{T(n)=\Theta(n\log n)} $$ - 最好情况：`Θ(n log n)`； - 平均情况：`Θ(n log n)`； - 最坏情况：`Θ(n log n)`； - 额外空间复杂度：`Θ(n)`。 > [!summary] 总结 > 归并排序将问题递归分成两个规模约为 `n/2` 的子问题，并在线性时间内完成归并。每层总代价为 `Θ(n)`，递归深度为 `Θ(log n)`，因此整体时间复杂度为 `Θ(n log n)`，额外空间复杂度为 `Θ(n)`。 # 问题 1 给定一个有n(n≥1)个整数的序列，要求求出其中最大连续子序列的和 （-2，11，-4，13，-5，-2）最大子序列为20 规定一个序列最大连续子序列和至少是0 对于含有n个整数的序列a\[0...n-1]若n=1，表示该序列仅含一个元素，如果该元素大于0，则返回该元素；反则返回0 n>1,取其中间位置$mid =\lfloor (n-1)/2 \rfloor$ 该子序列之可能出现3个地方 1. 该子序列完全落在左半部即a\[0...mid]中，采用递归求出最大连续子序列maxLeftSum 2. 该子序列完全落在右半部分a\[mid+1m,,n-1]中，采用递归求出最大连续子序列maxRightSum $$ \underset{\max RightSum}{\underbrace{a_{mid+1}a_{mid+2}...a_j...a_{n-1}}} $$ 3. 该子序列跨越序列a的中部而占据左右两部分 $$ \underset{\max LeftBorderSum}{\underbrace{a_ia_{i+1}...a_{mid}}}+\underset{\max RightBorderSum}{\underbrace{a_{mid+1...}a_j}} $$ $max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)$ ```cpp long maxSubSum(int a[],int left,int right) { int i,j; long maxLeftSum,maxRightSum; long maxLeftBorderSum,leftBorderSum; long maxRightBorderSum,rightBorderSum; if (left==right) //子序列只有一个元素 { if (a[left]>0) rerturn a[left]; else return 0; } maxLeftBorderSum=0,leftBorderSum=0; for (i=mid;i>=left;i--)//求出以左边加上a[mid]元素 { leftBorderSum+=a[i];//构成序列的最大和 if (leftBorderSum>maxLeftBorderSum) maxLeftBorderSum=leftBorderSum; } maxRightBorderSum=0,rightBorderSum=0; for (j=mid+1;jmaxRightBorderSum) maxRightBorderSum=rightBorderSum; } return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum); } ``` # 分治、贪心和动态规划 我们来彻底理清这三者的关系： 1. 分治法（Divide and Conquer） 特征：子问题独立，互不干扰，不包含公共子问题。 例子：归并排序、快速排序。 排序 \[5, 3, 8, 1]，分成 \[5, 3] 和 \[8, 1]。 排序 \[5, 3] 和排序 \[8, 1] 是完全独立的，互不影响。 算完这两个子问题，合并一下就完事了。 效率：因为子问题独立，所以分治法通常是把问题规模不断缩小，直接递归求解，不需要记录中间结果。 1. 动态规划（Dynamic Programming） 特征：子问题不独立，有重叠子问题（Overlapping Subproblems）。 例子：斐波那契数列、背包问题、最短路径。 算 F(5) 需要 F(4) 和 F(3)； 算 F(4) 也需要 F(3) 和 F(2)； 你会发现 F(3) 被算了两次。 如果直接用递归（分治法思想），会大量重复计算，效率极低。 动态规划的做法是：把算过的子问题答案存起来（备忘录/DP 表），下次直接查表，避免重复计算。 核心：最优子结构 + 重叠子问题 = 动态规划。 1. 贪心算法（Greedy） 特征：每一步都做出局部最优选择，希望最终得到全局最优解。 例子：找零钱（用最少硬币）、活动选择、霍夫曼编码。 贪心不关心子问题是否重叠。 它只关心：在当前这一步，我选哪个最划算？ 贪心不回溯，不存表，一条路走到黑。 核心：贪心选择性质 + 最优子结构 = 贪心算法。 如果子问题包含公共子问题，为什么不是贪心？ 因为贪心的核心不是“子问题重叠”，而是“每步选局部最优，不回头”。 子问题重叠 → 是动态规划的标志。 局部最优选择 → 是贪心的标志。 两者可以同时存在，但它们是不同的维度： 一个问题可能有重叠子问题，但贪心不适用（比如 0/1 背包）。 一个问题可能有贪心选择性质，但子问题不重叠（比如活动选择）。 1. 总结对比 | 算法 | 子问题关系 | 是否存表 | 核心思想 | | --- | --- | --- | --- | | 分治 | 独立、不重叠 | 不存 | 分而治之，递归合并 | | 动态规划 | 重叠、有公共子问题 | 存表 | 避免重复计算，自底向上或自顶向下+备忘录 | | 贪心 | 不一定重叠 | 不存 | 每步选局部最优，不回溯 | 分治：归并排序 左半部分排序和右半部分排序互不干扰，没有公共子问题。 动态规划：斐波那契 F(5) 依赖 F(4) 和 F(3)，F(4) 也依赖 F(3)，F(3) 被重复计算 → 重叠子问题 → 用 DP。 贪心：找零钱（硬币面额 1, 5, 10, 25） 每次选不超过剩余金额的最大面额硬币，不关心子问题是否重叠。 所以： 子问题独立 → 分治 子问题重叠 → 动态规划 每步选局部最优 → 贪心 对于一个规模为 n 的问题:若该问题可以容易地解决则直接解决，否则将其分解为 k 个规模较小的子问题。子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。即分治法。 关键在于**“分治”和“动态规划”不是互斥的分类，而是从不同角度描述算法的两个维度**。 ## 先澄清两个概念 **分治法**强调的是一种**求解结构**： - 把原问题拆成若干子问题 - 递归求解子问题 - 合并子问题的解 **动态规划**强调的是一种**优化手段**： - 子问题之间存在**重叠**（会被重复计算） - 通过**记忆化/表格**避免重复计算 ## 为什么会有交集？ 一个递归式如果满足： 1. 可以拆成子问题（分治特征） 2. 子问题**有重叠**（DP 特征） 那么它既是分治式的递归结构，又需要用 DP 来避免重复计算。 **典型例子：** - **归并排序**：分治，但子问题不重叠 → 纯分治 - **斐波那契 / 矩阵连乘 / 最优二叉搜索树**：分治式拆分，但子问题重叠 → 分治 + DP 以矩阵连乘为例，递归式是： $m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1]p[k]p[j] }$ 这明显是“拆成子区间再合并”的分治形式，但不同的 `(i,j)` 会反复用到相同的子区间，所以必须用 DP 存表。 ## 你可能是被教材的“二分法”误导了 很多教材把“分治”和“动态规划”并列成两类，容易让人以为它们互斥。更准确的说法是： |维度|分治|动态规划| |---|---|---| |关注点|问题怎么拆、怎么合|子问题重叠时怎么不重复算| |子问题关系|通常独立|通常重叠| |是否可共存|✅ 可以|✅ 可以| 所以“分治法的动态规划”这个说法，准确理解是：**用分治的递归结构来划分子问题，再用 DP 的记忆化/递推来消除重叠子问题的重复计算**。两者描述的是同一算法的不同侧面，并不矛盾。**分治和 DP 本身没有完全对立面；它们只是在“子问题是否重叠”这个维度上，恰好站在了两端。** # 分成子问题为什么可以成 n/2 1. 归并排序的子问题规模 归并排序把规模为 \(n\) 的问题分成两个子问题，大小分别为： $$ \lceil n/2 \rceil, \lfloor n/2 \rfloor $$ 这两个数最多差 1： $$ \lceil n/2 \rceil - \lfloor n/2 \rfloor \le 1 $$ 当 \(n\) 很大时，这点差异相对于“除以 2”来说非常小。 因此，在分析增长阶时，可以“偷懒”把两个子问题都写成： $$ n/2 $$ 也就是说，忽略向上取整和向下取整，通常不会影响分治递归解的增长阶。 2. 递归式的简化写法 因此，后面写归并排序的递归式时，可以放心写成： $$ T(n) = 2T(n/2) + \Theta(n) $$ 而不必写成更精确但更繁琐的形式： $$ T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) $$ 其中： $$ 2T(n/2) $$ 表示两个规模约为 \(n/2\) 的子问题； $$ \Theta(n) $$ 表示合并两个有序子数组所需的时间。 3. 基础情况 对于足够小的输入规模 \($n < n_0$\)，算法运行时间是常数，所以： $$ T(n) = \Theta(1) $$ 因此默认基础情况就是： $$ T(n) = \Theta(1), \quad n < n_0 $$ 写递归式时，通常不显式写出基础情况。 # T(n/b)与 cn 与代价 任何一层、任何一个节点的代价，都可以写成： $$\text{代价} = \text{cost} \times \text{times}$$ 区别只在于：“cost”填什么、“times”填什么。 | 视角 | cost（单个工作量） | times（数量） | 结果 | |------|---------------------|---------------|------| | 递归式里的递归项 | $T(n/b)$ | $a$ | $a \cdot T(n/b)$ | | 递归树展开的当前层 | $c(n/b)$ | $a$ | $a \cdot c(n/b)$ | 两者的乘法结构完全相同，都是“数量 × 单个工作量”。 这里的“代价”指的是**运行时间（或基本操作次数）**。 关键在于：递归树上一个节点的代价，只计算它自己完成的分解和合并工作，**不包含递归处理子问题的时间**，因为那些时间会在下层节点中计算。 · $T(n/b)$ 是方程里的未知量，代表"子问题最终要花多少时间”——但你还不知道它是多少； · $c(n/b)$ 是展开树时每个节点实际执行的物理操作——这个是已知的(就是一次 Merge 的代价) 。 从 $T(n/b)$ 到 $c(n/b)$,就是"把未知的递归项，替换成已知的当前层操作代价"的过程。这正是递归树展开在做的事。 $aT(n/b)$ 是结构，不是时间项。 - 它不参与任何一层的加法；它就是递归树本身—— $a$ 定分叉，$n/b$ 定缩减。 - 真正逐层相加的，是每个节点当前亲手做的 $D(n) + C(n)$。 - 递归时间不单独出现，而是散落在子树各层的 $D + C$ 中，加完所有层就自动算进去了。 每层为什么是 $c_2 n$？ 第 $i$ 层有 $2^i$ 个节点，每节点规模 $n/2^i$，单节点代价 $c_2(n/2^i)$： $$2^i \cdot c_2 \frac{n}{2^i} = c_2 n$$ 节点数翻倍与规模减半恰好抵消，故每层代价恒定。 总和： $$ \underbrace{c_2 n}_{\text{每层}} \times \underbrace{\log n}_{\text{层数}} + \underbrace{c_1 n}_{\text{叶层}} = \Theta(n \log n)$$ 一句话：把“递归的时间计算”转化成了“树的逐层空间累加”。 而 $T(n/b)$ 那一项呢？它不消失，它变成了下一层——下一层的节点数、规模，正是 $a$ 和 $n/b$ 决定的。所以你继续往下一层展开，就是在继续“兑现”$T(n/b)$。 $\begin{aligned}\\aT(n/b)&=a{\left[\left.aT(n/b^2)+c(n/b)\right.\right]}\\&=a^2T(n/b^2)+ac(n/b)\\&=a^2\left[aT(n/b^3)+c(n/b^2)\right]+ac(n/b)\\&=\ldots\\&=\underbrace{a^kT(n/b^k)}_\text{最底层,变成常数}+\underbrace{\sum_{i=0}^{k-1}a^ic(n/b^i)}_{\text{各层 cost }\times\text{times 之和}}\end{aligned}$ # c 1,c 2 与 c 1. 原问题（Θ 版本）：太抽象，无法用初等代数直接求解。 2. 为了求解，我们做了妥协（简化）：假设 $n$ 是 2 的幂。忽略小数的烦恼。 3. 为了运算，我们赋予了实体（精确化）：把 $\Theta(1)$ 具象化为 $c_1$，把 $\Theta(n)$ 具象化为 $c_2 n$。 4. 最终得出 $c_1$ 和 $c_2 n$ 版本的答案后，再返回到 $\Theta$ 形式（结论）：你会发现 $c_1$ 和 $c_2$ 最终还是会吸收回 $\Theta$ 或 $O$ 记号中。 关于 $c_1$:在递归的基准情况 (base case)中，我们常说当问题规模 $n=1$ 时，解决它需要常数时间 $c_1$。但在现实计算机中，处理不同数据的规模为 1 的操作，时间可能会有细微差别，不可能是一个绝对固定的值。 关于 $c_2n$: 我们假设分治和合并的步骤耗时与 $n$ 成严格的正比线性关系 (即 $c_2n)$ 。但在实际运行中，由于计算机内存、缓存、指令流水线等硬件因素，这个时间往往不是完美的线性关系。 其中常量 `c` 表示规模为 1 的问题所需时间，以及分解步骤和合并步骤处理每个数组元素所需的时间。不同层的常量可能不同：规模为 1 的问题使用一个常量表示，分解和合并每处理一个元素也可能使用另一个常量。可以分别用上界常量或下界常量估计它们。