时间复杂度分析

1. 引言递归算法的时间复杂度通常用递归式表示。本文介绍三种分析递归式的工具：递归树法、主定理与 Akra-Bazzi 定理，并通过实例帮助读者掌握递归复杂度的分析方法。2. 时间复杂度基础2.1 什么是时间复杂度时间复杂度描述算法执行时间随输入规模增长的变化趋势，常用大 O 记号表示上界。常见复杂度从低到高：O(1)O(1)O(1)、O(log⁡n)O(\log n)O(logn)、O(n)O(n)O(n)、O(nlog⁡n)O(n \log n)O(nlogn)、O(n2)O(n^2)O(n2)、O(2n)O(2^n)O(2n)。下面列出常见算法的时间复杂度，便于对照记忆：递归算法的时间复杂度用递归式表示，如归并排序：T(n)=2T(n/2)+O(n) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)含义：解决规模为nnn的问题，需解决 2 个规模为n/2n/2n/2的子问题，再加上合并所需的O(n)O(n)O(n)时间。3. 递归树法3.1 基本思想递归树法把递归式的展开过程画成一棵树，每个节点代表一个子问题的开销，把所有层开销累加即得总复杂度。以归并排序为例：T(n)=2T(n/2)+O(n) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)递归树如下：n / \ n/2 n/2 / \ / \ n/4 n/4 n/4 n/4每层开销都是nnn，树高为log⁡2n\log_2 nlog2​n，因此总复杂度为Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn)。3.2 递归树法的步骤展开递归式：把每层的分解与合并开销写在节点上。计算每层总开销：将同一层所有节点开销相加。确定树高：子问题规模从 n 缩小到常数所需的层数。累加所有层：将各层开销求和。3.3 递归树法示例示例一：二分查找T(n)=T(n/2)+O(1) T(n) = T(n/2) + O(1)T(n)=T(n/2)+O(1)每层只有一个节点，开销为O(1)O(1)O(1)，树高为log⁡2n\log_2 nlog2​n，因此T(n)=Θ(log⁡n)T(n) = \Theta(\log n)T(n)=Θ(logn)。示例二：子问题规模不等T(n)=T(n/3)+T(2n/3)+O(n) T(n) = T(n/3) + T(2n/3) + O(n)T(n)=T(n/3)+T(2n/3)+O(n)每层总开销为nnn，树高由最长路径决定，为log⁡3/2(n)\log_{3/2}(n)log3/2​(n)，因此T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n)T(n)=Θ(nlogn)。递归树法直观但不够严谨，更严格的证明通常借助主定理或 Akra-Bazzi 定理。4. 主定理（Master Theorem）4.1 主定理的适用条件主定理适用于形如下式的递归式：T(n)=aT(n/b)+f(n) T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)其中 a ≥ 1 为子问题个数，b 1 为规模缩减比例，f(n) 为分解与合并的开销。4.2 主定理的三种情况主定理通过比较f(n)f(n)f(n)与nlog⁡ban^{\log_b a}nlogb​a的渐近大小关系划分三种情况。情况一：递归主导当f(n)=O(nlog⁡ba−ε)f(n) = O(n^{\log_b a - \varepsilon})f(n)=O(nlogb​a−ε)（ε0\varepsilon 0ε0）时：T(n)=Θ(nlog⁡ba) T(n) = \Theta(n^{\log_b a})T(n)