4 复杂度分析

4.1 语句频度与运行时间的抽象

语句频度与事前分析估算

• 是什么：语句频度（statement frequency）指算法中某条语句在算法执行过程中被重复执行的次数。
• 为什么：同一算法在不同机器、编译器与输入下实测耗时不同，无法用绝对时间比较；事前分析（pre-analysis estimation）改用「基本操作次数随规模 n 的增长」作为与实现无关的度量，语句频度是最基本的计数单位。
• 怎么用：把算法写成语句序列，为每条语句写出其频度（关于 n 的函数），累加得到运行时间T(n)T(n)T(n)，最后取渐近阶。
• 边界：频度的精度取决于「基本操作」的选取；当执行次数依赖输入数据（分支、条件提前退出）时，频度只能得到特定情形的计数值，需借 4.5 的最好/最坏/平均框架区分。

/* 统计循环体内语句的频度（C17）*/#include<stdio.h>longcount=0;/* 语句频度计数器 */voidf(intn){for(inti=1;i<=n;++i)/* 外层频度 n */for(intj=i;j<=n;++j)/* 内层合计 n(n+1)/2 */++count;/* 频度 n(n+1)/2 */}intmain(void){for(intn=1;n<=5;++n){count=0;f(n);printf("n=%d -> %ld\n",n,count);}return0;}

输出：1、3、6、10、15，即n(n+1)/2n(n+1)/2n(n+1)/2，与T(n)=Θ(n2)T(n)=\Theta(n^2)T(n)=Θ(n2)一致。

为什么要进行复杂度分析

同一问题可能存在多种算法，比较其优劣需要不依赖具体运行环境的评价标准，复杂度分析提供了这一标准：

直观对比：当n=106n = 10^6n=106时：

• O(nlog⁡n)O(n \log n)O(nlogn)算法约2×1072\times10^72×107次操作（可秒级完成）
• O(n2)O(n^2)O(n2)算法约101210^{12}1012次操作（可能需数小时至数天）

这不是"快一点"和"慢一点"的区别，而是可行与不可行的质变。

复杂度的定义

核心定义：复杂度是描述算法资源消耗随输入规模 n 增大的增长趋势的函数。

性质：

• 不是绝对度量（不以毫秒或字节为单位）
• 独立于硬件、编译器和具体输入数据
• 核心价值在于建立一套普适、可比较的算法效率评价语言

T(n)=算法基本操作次数 T(n)=\text{算法基本操作次数}T(n)=算法基本操作次数

S(n)=算法额外辅助空间 S(n)=\text{算法额外辅助空间}S(n)=算法额外辅助空间

时间复杂度的定义

时间复杂度是算法中基本操作执行的次数，作为问题规模 n 的函数T(n)T(n)T(n)。

基本操作的选取原则：

• 选择算法中最深层循环内的操作
• 或选择执行频率最高的关键操作

问题规模 n 的确定：不同问题中 n 的含义不同，需根据具体场景定义。

复杂度计算规则

思想：算法的时间复杂度是其各组成部分执行代价的总和。逐条统计每条语句不现实，工程上采用三条简化规则从整体上估算：

示例：对 n 个元素的数组先做O(n)O(n)O(n)扫描再做O(nlog⁡n)O(n \log n)O(nlogn)排序，总复杂度 =O(n)+O(nlog⁡n)=O(nlog⁡n)O(n) + O(n \log n) = O(n \log n)O(n)+O(nlogn)=O(nlogn)（加法法则 + 忽略规则）。

• 三条规则的严格数学基础是渐近记号的运算性质（见 3.2）；下两节分别对加法法则与乘法法则给出详细推导与示例。

算法分析的六步流程

复杂度分析的核心思维

4.2 循环结构分析

加法法则——顺序执行

若算法的两个部分的时间复杂度分别为O(f(n))O(f(n))O(f(n))和O(g(n))O(g(n))O(g(n))，则总时间复杂度为：

O(f(n))+O(g(n))=O(max⁡(f(n),g(n))) O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))O(f(n))+O(g(n))=O(max(f(n),g(n)))

含义：总复杂度由增长最快的主项决定，低阶项与常数在大 n 面前可忽略。

示例：

• 先O(n)O(n)O(n)遍历再O(nlog⁡n)O(n \log n)O(nlogn)排序 →O(nlog⁡n)O(n \log n)O(nlogn)
• O(n2)+O(n)=O(n2)O(n^2) + O(n) = O(n^2)O(n2)+O(n)=O(n2)

乘法法则——嵌套循环

若外层循环复杂度为O(f(n))O(f(n))O(f(n))，内层为O(g(n))O(g(n))O(g(n))，则嵌套总复杂度为：

O(f(n))⋅O(g(n))=O(f(n)⋅g(n)) O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))O(f(n))⋅O(g(n))=O(f(n)⋅g(n))

代码示例：

• 代码说明：示意伪码（非可编译代码），非 C17 基准。

// 单层循环 → O(n) for i = 1 to n do x = x + 1 // 嵌套循环 → O(n²) for i = 1 to n do for j = 1 to n do x = x + 1 // 对数循环 → O(log n) i = 1 while i < n do i = i * 2 // 依赖外层变量 → 精确求和仍为 O(n²) for i = 1 to n do for j = i to n do x = x + 1 // 总次数 = n + (n-1) + ... + 1 = n(n+1)/2 → O(n²)

T(n)=n+(n−1)+⋯+1=n(n+1)2=O(n2) T(n)=n+(n-1)+\cdots+1=\frac{n(n+1)}2=O(n^2)T(n)=n+(n−1)+⋯+1=2n(n+1)​=O(n2)

4.3 递归结构分析

递归结构分析的要义

• 是什么：递归结构分析指对「函数调用自身」的算法，把总代价表示为子问题代价的函数T(n)T(n)T(n)，再求解该递推关系。
• 为什么：递归每次把问题规模缩小后重复调用，总代价无法靠简单语句频度相加，必须「分而计之」再合并。
• 怎么用：① 数每次调用产生的子问题个数与规模；② 累加非递归部分（分解/合并）的代价；③ 写出T(n)T(n)T(n)与递归基；④ 用 4.4 与第 5 章的方法求解。
• 边界：递归的空间代价等于最大递归深度而非调用总数（见 7.2）；交错递归（如T(n)=T(n−1)+T(n−2)T(n)=T(n-1)+T(n-2)T(n)=T(n−1)+T(n−2)）不能套用主定理，需用递归树或特征方程法。

/* 递归与迭代二分查找：比较次数（C17）*/#include<stdio.h>intrec_cmp,it_cmp;intrec_bsearch(constint*a,intlo,inthi,intkey){if(lo>hi)return-1;intmid=lo+(hi-lo)/2;++rec_cmp;if(a[mid]==key)returnmid;if(a[mid]<key)returnrec_bsearch(a,mid+1,hi,key);elsereturnrec_bsearch(a,lo,mid-1,key);}intit_bsearch(constint*a,intn,intkey){intlo=0,hi=n-1;while(lo<=hi){intmid=lo+(hi-lo)/2;++it_cmp;if(a[mid]==key)returnmid;if(a[mid]<key)lo=mid+1;elsehi=mid-1;}return-1;}intmain(void){inta[1024];for(inti=0;i<1024;++i)a[i]=i;for(intn=8;n<=1024;n*=2){rec_cmp=it_cmp=0;rec_bsearch(a,0,n-1,-1);/* 最坏：查找失败 */it_bsearch(a,n,