递归复杂度分析主要是通过递归关系式来推导
这类分析的核心是理解递归函数的调用模式和所需要的计算量
基本方法和技巧如下
递归关系式
递归算法的复杂度通常可以用递归关系式来表示
例如，一个递归函数可能看起来像这样
T(n) = T(n-1) + O(1)
这表示函数需要处理大小为n的问题，递归地调用自身处理规模为n-1的子问题，并且每次递归调用执行的工作量是O(1)
递归关系式是推导复杂度的基础
写递归关系式
编写递归关系式的关键是理解递归算法的结构，尤其是递归调用的次数和每次调用所做的工作量
递归关系式通常反映了递归过程中的分治策略，既将大问题分解为小问题，再通过合并小问题的解来获得最终解
步骤
- 确定递归调用的次数 递归通常会将问题分解成若干个子问题。需要确定每次递归调用的次数。例如，如果每次将问题规模分成两半，则递归会调用两次
- 确定子问题的规模 确定每次递归调用中子问题的规模。通常每次递归调用会使问题的规模减少一定比例（如减半、减少1等）
- 计算每次递归的工作量
计算每次递归所需要的额外计算量（不包括递归调用）。例如，如果问题规模为
n，合并操作可能需要O(n)的时间 - 写出递归关系式 基于上述三点，构建递归关系式。常见的递归关系形式通常为 $$T(n)=aT(n/b)+O(n^d)$$
其中：
a是子问题的个数b是每次递归将问题减少规模的倍数n^d是每次递归调用的工作量
常见递归模式及其递归关系式
二分法（Divide and Conquer）
对于将问题规模减半的递归，通常形式是 $$T(n)=aT(n/b)+O(n^d)$$
a：每次递归生成的子问题的数量b：每次递归将问题规模缩小的倍数n^d：每次递归调用的计算量，通常是合并阶段的时间复杂度
示例：归并排序
- 归并排序每次将问题分成两个子问题，每个子问题的大小为
n / 2，并且每一层合并的操作需要O(n)时间 - 递归关系式 $$T(n)=2T(n/2)+O(n)$$
- 这个关系式表示，每次递归有两个子问题，每个子问题规模为
n / 2，而每层的合并过程需要O(n)时间
减治法（Decremental）
如果每次递归只是将问题规模减小一小步，比如减1，那么递归关系式的形式通常是
$$T(n)=T(n-1)+O(1)$$
- 递归调用一次，问题规模减小
1，每次计算所需的时间是O(1)
示例：计算阶乘
- 计算阶乘的递归过程每次调用都会减小问题规模
n-1，直到n=1 - 递归关系式 $$T(n)=T(n-1)+O(1)$$
多分支递归
如果递归问题分为多个子问题并行解决（例如，快速排序），则递归关系式可能有更多的分支
示例：快速排序
- 快速排序每次选择一个基准元素，将数组分成两部分，然后递归排序每个部分。假设每次都能将数组均匀分割，则递归关系式为 $$T(n)=2T(n/2)+O(n)$$
- 其中，
O(n)是每次划分过程的工作量，2T(n / 2)表示两个子问题的递归调用
树形递归
对于一些问题，递归调用的结构是树形的，即每个子问题又分解为多个子问题。例如，分治算法中的某些计算问题
示例：汉诺塔
- 汉诺塔的递归解法每次将
n个盘子的移动分解为三个子问题：移动n-1各盘子，移动最底下的盘子，再移动n-1个盘子。递归关系式是 $$T(n)=2T(n-1)+O(1)$$ - 每次递归都将盘子数减去
1，且每层的操作为O(1)
总结
假设有一个递归算法，写递归关系式的步骤如下
- 分析递归调用的次数 每次递归调用多少个子问题？每个子问题的规模是多少？
- 分析递归计算量
每次递归的工作量是多少？通常是
O(b)或O(log n)，取决于问题的特点 - 写出递归关系式 根据上面的分析，写出递归关系式
示例
假设有一个递归算法，将问题分解为两个子问题，并且每次计算的工作量是线性的O(n)
$$T(n)=2T(n/2)+O(n)$$
这表示问题分成两个大小为n / 2的子问题，每次合并的计算量是O(n)
递归树法
递归树是一种图形化的方法，用来表示递归调用过程中的各层计算。通过递归树，我们可以观察每层的工作量，并根据树的深度和每层的计算量来计算总的复杂度
递归树法的基本步骤
- 绘制递归树：将递归过程展开为一棵树。每个节点代表一次递归调用，每一层代表递归的深度
- 计算每一层的工作量：每个节点的工作量通常是
O(n),O(n/2),O(n^2)等，取决于算法的具体实现 - 计算每一层的总工作量：通过观察每一层的节点数量和每个节点的工作量，计算该层的总工作量
- 累加所有层的工作量：从根到叶子，累加所有层的工作量，得到总的时间复杂度
示例1：归并排序（Merge Sort）
归并排序的递归关系式是
$$T(n)=2T(n/2)+O(n)$$
- 递归树的构建
- 每一层都有两个子问题，每个子问题的规模是当前问题规模的一半
- 每一层的合并过程工作量是
O(n)，即每层都需要遍历整个数组来合并两个已排序的部分
展开递归树
- 第0层：
T(n)，工作量是O(n) - 第1层：
2T(n/2)，每个子问题的规模是n/2，工作量是O(n/2)每个节点，所以总工作量是O(n) - 第2层：
4T(n/4)，每个子问题的规模是n/4，工作量是O(n/4)每个节点，所以总工作量是O(n) - 第k层：
2^k T(n / 2^k)，每个子问题的规模是n / 2^k，工作量是O(n / 2^k)每个节点，所以总工作量是O(n)
可以看到，每一层的总工作量都是O(n)
- 递归树的深度：树的深度是
log n，因为每次递归调用问题的规模都减半，直到规模为1
总工作量
- 每一层的工作量都是
O(n)，树的深度是log n - 总的工作量是各层的工作量之和 $$O(n)+O(n)+O(n)+···+O(n)=O(nlogn)$$
所以，归并排序的时间复杂度是O(n log n)
示例2：快速排序（Quick Sort）
快速排序的递归关系式是
$$T(n)=2T(n/2)+O(n)$$
- 递归树的构建
- 每次递归将问题分成两个大小为
n/2的子问题 - 每层的分区过程（即选择基准元素并进行划分）需要遍历整个数组，工作量是
O(n)
- 每次递归将问题分成两个大小为
展开递归树
- 第0层：
T(n)，工作量是O(n) - 第1层：
2T(n/2)，每个子问题的规模是n/2，工作量是O(n/2)每个节点，所以总工作量是O(n) - 第2层：
4T(n/4)，每个子问题的规模是n/4，工作量是O(n/4)每个节点，所以总工作量是O(n) - 第k层：
2^k T(n / 2^k)，每个子问题的规模是n / 2^k，工作量是O(n / 2^k)每个节点，所以总工作量是O(n)
每一层的工作量仍然是O(n)
- 递归树的深度：树的深度是
log n，因为每次递归将问题规模减半，直到规模为1
总工作量
- 每一层的工作量都是
O(n)，树的深度是log n - 总的工作量是
$O(n)+O(n)+O(n)+···+O(n)=O(n log n)$
所以，快速排序的时间复杂度是O(n log n)
递归树法的总结与技巧
- 每层的工作量：通常，递归的每一层都会有一定的工作量，比如在归并排序中，每一层的合并过程的工作量是
O(n) - 递归树的深度：递归树的深度取决于每次递归如何缩小问题规模。通常是对数级别（
log n），除非递归关系中每次递归调用的规模变化更复杂（如n-1） - 树的结构：树的每一层的节点数量和每个节点的工作量是递归关系的重要信息。通过观察树的形状和每层的工作量，可以轻松推导总时间复杂度
- 合并所有层的工作量：通过将每一层的工作量累加，得到总的时间复杂度
递归树法特别适用于简单的分治算法（如归并排序，快速排序等），它直观易懂，有助于清晰地理解算法的时间复杂度。对于更复杂的递归关系，可能需要结合主定理等其他方法
主定理(Master Theorem)
主定理是解决递归关系的一种强大工具，尤其用于分析递归算法的时间复杂度。它简化了递归式的求解，避免了手动展开递归树或使用代入法的复杂性。主定理适用于具有特定形式的递归关系，通常表现为：
$T(n) = aT(n / b) + O(n^d)$
- a是递归调用的次数（即每次递归分成多少子问题）
- b是每个子问题的规模（及子问题的大小是原问题的$$1/b$$）
- d是合并子问题的工作量，通常是对子问题的处理时间或合并操作的时间复杂度
主定理给出了一个简单的方式来确定递归复杂度
- Case1：如果$a>b^d$，则复杂度为$O(n^{log_ba})$
- 这种情况意味着递归树的工作量主要来自子问题的解，即子问题的规模递归增长得比合并的工作量要多
- Case2：如果$a=b^d$，则复杂度为$O(n^d logn)$
- 在这种情况下，递归树的高度和每一层的合并工作量是均衡的。每层的工作量增长的速度与递归调用的次数是相同的
- Case3：如果$a<b^d$，则复杂度为$O(n^d)$
- 这里，合并的工作量比递归调用的工作量要大，递归解的计算成本很低，而大部分时间花在合并的步骤上
示例
- 归并排序：$T(n)=2T(n/2)+O(n)$
- 这里$a=2,b=2,d=1$
- 由主定理第二种情况可得，时间复杂度为$O(nlogn)$
- 二分查找：$T(n)=T(n/2)+O(1)$
- 这里$a=1,b=2,d=0$
- 由主定理第一种情况可得，时间复杂度为$O(logn)$
- 矩阵乘法的分治算法：T(n)=8T(n/2)+O(n^3)
- 这里$a=8,b=2,d=3$
- 由主定理第一种情况可得，时间复杂度为$O(n^3)$
主定理的推导
推导思路：分析递归关系的总时间复杂度，用递归树的思想来理解递归调用的展开
- 递归树的结构
- 假设从原问题开始（规模是n），每次递归将问题拆分为a各规模为n/b的子问题，并且每层的合并工作量是$O(n^d)$
- 递归树的根节点表示原问题，接下来的每一层表示递归过程中产生的子问题
- 每一层的工作量
在每一层，合并子问题的工作量为$O(n^d)$，而每层的子问题数目会增加。具体来说
- 第0层（根节点）只有一个问题，合并工作量为$O(n^d)$
- 第1层有a个子问题，每个子问题的规模是$n/b$，所以合并每一层的工作量是$a*O((n/b)^d)=O(n^d)$
- 第2层有$a^2$个子问题，每个子问题的规模是$n/b^2$，所以合并每一层的工作量是$a^2*O((n/b^2)^d)=O(n^2)$
- …
可以看到，直到第k层，每层的总工作量大约是$O(n^d)$，因为每层的子问题数目是指数增长的，而每个子问题的规模是指数缩小的
递归树的总高度 递归树的高度可以通过递归关系来确定。在每一层，问题的规模都被缩小来b倍。因此，递归树的总高度是$log_b n)，因为在第k层时，子问题的规模为$n/b^k$，当子问题的规模降到1时，k达到$log_b n$
总工作量 如果递归树的高度为$log_b n$，并且每一层的工作量为$O(n^d)$，那么递归树的总工作量是
$总工作量 = 每层工作量 * 层数=O(n^d)*O(log_b n)$
这就是在$a=1$和$b=2$的情况下，归并排序的典型时间复杂度分析（$O(n log n)$）
如何使用主定理
- 识别递归式：确保递归式是类似于$T(n)=aT(n/b)+O(n^d)$这样的标准形式
- 确定参数：找到a, b, d的值
- 选择正确的情况：根据a, b, d的关系，选择适当的主定理情况来计算时间复杂度
- 主定理通常用于处理较常见的递归形式，对于更复杂的递归关系，可能需要用其他方法（如递归树法、代入法等）来求解
- 递归式的结构必须满足标准形式（即只包含一个递归项和一个合并项），如果有多个递归项或非多项式合并项，就不适用于主定理
递归展开法（递归树法）
这尤其适用于分析分治算法的时间复杂度。它通过将递归关系展开成一棵树，然后累加每一层的工作量，最终求得递归式的总复杂度
基本思想
通过将递归关系逐层展开，直到到达基准情况（通常是$T(1)=O(1)$），然后计算每一层的工作量，最后将所有层的工作量加总，得到总体的时间复杂度
求解步骤
- 写出递归关系
给定一个递归关系，一般是类似于：
$T(n)=aT(\frac{n}{b})+O(n^d)$
其中- $a$是每次递归产生的子问题的个数
- $b$是每个子问题的规模（每次递归时问题的规模缩小的倍数）
- $O(n^d)$是每次合并的时间复杂度（即每层的合并工作量）
- 展开递归关系 将递归关系展开，直到递归到达基准情况。每层都会产生新的子问题，并且每层的工作量会随子问题规模的变化而变化
- 计算每一层的工作量 每一层的工作量是递归关系中与问题规模相关的项。通常情况下，递归关系中包含一个$O(n^d)$的项表示每层的合并工作量
- 累加各层的工作量 将每一层的工作量进行累加，得到总的工作量。这个累加通常会形成一个数学序列（例如等比数列或等差数列），可以通过求和公式进行简化计算
- 得出时间复杂度 根据递归树的高度和每层的工作量，计算出递归关系的总体时间复杂度
示例：递归展开法分析$T(n)=2T(n/2)+O(n)$
- 展开递归关系
首先，逐层展开递归关系
- 第一层（原问题，规模为$n$）
$T(n)=2T(n/2)+O(n)$ - 第二层：将$T(n/2)$展开
$T(n)=2[2T(n/4)+O(n/2)]+O(n)$
展开后
$T(n)=2^2T(n/4)+2O(n/2)+O(n)$ - 第三层：将$T(n/4)展开$
$T(n)=2^3T(n/8)+2^2O(n/4)+2O(n/2)+O(n)$
以此类推，每次递归都会将问题规模缩小一半
- 第一层（原问题，规模为$n$）
- 确定递归树的高度 在这个递归关系中，问题的规模每次都被缩小为原来的一半。因此，递归树的高度为$log_2 n$\
- 计算每一层的工作量
- 第0层（根节点）：工作量是$O(n)$
- 第1层：工作量是$2*O(n/2)-O(n)$
- 第2层：工作量是$4*O(n/4)=O(n)$
- 第3层：工作量是$8*O(n/8)=O(n)$
以此类推，每一层的工作量都是$O(n)$
4. 累加各层的工作量
递归树的每一层的工作量都是$O(n)$，因此总的工作量是
$O(n)+O(n)+O(n)+…$
共有$log_2 n$层，所以总工作量为
$T(n)=O(nlog n)$
5. 得出时间复杂度
根据递归展开法，得出最终的时间复杂度为$T(n)=O(nlog n)$
迭代法
迭代法也叫循环展开法，特别用于求分支算法的时间复杂度。它是通过将递归过程转化为循环（或等价的重复操作）来推导出时间复杂度。
与递归展开法不同，迭代法更侧重于使用反复展开的形式来计算总的工作量，特别是对于一些递归关系较为复杂的情况，迭代法往往更有效
如果递归关系不适合直接使用主定理，可以通过迭代法来求解复杂度。通过不断展开递归关系，可以找到一个通用模式，然后总结出时间复杂度
基本思想
通过将递归关系转换成一个或多个重复操作（即循环），然后通过逐步展开递归过程，分析每一步的工作量。最终，通过累加每一层的工作量得到整个算法的时间复杂度
求解步骤
迭代法一般包括以下几个步骤：
- 写出递归关系：
首先写出递归关系的标准形式，例如：
$T(n)=aT(n/b)+O(n^d)$
或者其他类似的递归形式 - 初始化迭代公式 将递归关系转化为迭代形式。基本的思路是通过不断代入递归式，逐步展开
- 反复展开递归公式 对递归关系进行多次迭代展开，直到最终得到一个明显的规律或基准情况。每次展开时，我们会看到每一层的工作量
- 累加每一层的工作量 对展开后的各层工作量进行累加，通常每一层的工作量会跟层数和问题规模的某个关系有关。最终，可以求得总的工作量
- 简化求和表达式 将各层的工作量求和，如果有求和的公式（如等比数列、等差数列等），可以使用这些公式来简化计算
示例：递归关系的迭代法
考虑一个常见的递归关系：
$T(n)=2T(n/2)+O(n)$
通过迭代法求解其时间复杂度
初始化递归关系 首先，写出递归式的初始形式
$T(n)=2T(n/2)+O(n)$展开递归关系
- 第一层：$T(n)=2T(n/2)+O(n)$
- 第二层：$T(n/2)=2T(n/4)+O(n/2)$
代入上式得到：
$T(n)=2*[2T(n/4)+O(n/2)]+O(n)$
展开后
$T(n)=2^2T(n/4)+2O(n/2)+O(n)$ - 第三层：$T(n/4)=2T(n/8)+O(n/4)$
代入上式：
$T(n)=2^3T(n/8)+2^3O(n/4)+2O(n/2)+O(n)$
通过继续展开递归式，可以发现递归树每一层的工作量逐渐减少
确定递归树的高度
递归树的高度是 $log_2 n$（因为每次递归将问题规模缩小为原来的一半，直到问题规模为1）计算每一层的工作量
每一层的工作量是- 第0层：$O(n)$
- 第1层：$O(n/2)$
- 第2层：$O(n/4)$
- 第k层：$O(n/2^k)$
累加每一层的工作量 将每一层的工作量累加起来，总工作量为：
$O(n)+O(n/2)+O(n/4)+…$
这是一个等比数列，首项为O(n)，公比为1/2，根据等比数列的求和公式，可以得到：
$S=O(n)*(1+1/2+1/4+…)=O(n)*2=O(n)$
代入法
代入法特别适用于一些较为复杂的递归式，代入法通过猜测递归式的解并用数学归纳法进行证明
其基本思路是：假设递归关系的时间复杂度满足某种形式，然后通过归纳法验证这个假设，进而确定递归的时间复杂度
基本思想
- 假设解的形式：首先，猜测一个递归式的解（时间复杂度），通常通过经验或者直觉来进行猜测
- 代入递归关系：将猜测的解代入递归关系中，并通过数学归纳法进行验证
- 验证并推导：通过归纳法证明递归关系在每个阶段都成立，从而得出正确的时间复杂度
代入法的核心步骤是使用数学归纳法逐步证明假设的时间复杂度解是正确的
求解步骤
写出递归关系 给定递归关系，通常会是类似如下的形式
$T(n)=aT(n/b)+O(n^d)$
或其他形式的递归式猜测一个解 根据递归式的特点，猜测解的形式。假设解的形式为$T(n)=O(n^k)$或者类似的形式
例如，针对递归关系$T(n)=2T(n/2)+O(n)$，可以猜测$T(n)=O(nlogn)$作为解代入递归关系并展开 将猜测的解代入到递归关系中，并展开验证是否满足
进行数学归纳法验证 使用数学归纳法证明，对于所有n,递归关系都成立
得出结论 如果通过归纳法证明了递归关系成立，那么就可以确认时间复杂度的解是正确的
示例：使用代入法求解$T(n)=2T(n/2)+O(n)$
写出递归关系 假设有如下递归关系：
$T(n)=2T(n/2)+O(n)$猜测解的形式 猜测的时间复杂度的解是$T(n)=O(nlogn)$。需要用代入法来演这个这个猜测
代入递归关系 首先，经猜测的解代入递归式。假设$T(n)<=Cnlogn$（其中C是常数，n为问题规模）：
$T(n)=2T(n/2)+O(n)$
假设$T(n)<=Cnlogn$，那么：
$T(n/2)<=C(n/2)log(n/2)=Cn/2log(n/2)$
代入原递归式：
$T(n)<=2(Cn/2log(n/2))+O(n)$
$T(n)<=Cnlog(n/2)+O(n)$
利用对数的性质：$log(n/2)=logn-log2$，可以得到
$T(n)<=Cn(log n - log 2)+O(n)$
$T(n)<=Cnlog n - Cnlog 2+O(n)$
显然，Cnlog2是常数项，且$O(n)$的项可以看作是较小的项，因此：
$T(n)=O(nlog n)$使用数学归纳法证明 为了完成归纳法，需要验证猜测的形式对于所有n都成立。假设对于某一$n=k$时，$T(k)<=Cklogk$成立，然后验证对$n=k+1$时也成立
- 基准情况：当$n=1$时，递归关系的复杂度为常数$T(1)=O(1)$，显然符合$O(nlog n)$的形式
- 归纳假设：假设$T(k)<=Cklogk$对于某个k成立
- 归纳步骤：根据递归关系，有
$T(k+1)=2T(\frac{k+1}{2})+O(k+1)$
代入归纳假设，得出最终结果
因此，通过数学归纳法可以证明$T(n)=O(nlogn)$是正确的