【数据结构】 时间复杂度
目录
一、循环结构类时间复杂度分析
1. 单层循环
2. 嵌套循环
二、递归类时间复杂度分析
三、链表操作类时间复杂度
四、特殊循环条件类
五、排序算法复杂度对比
六、易错点总结
仅供参考
一、循环结构类时间复杂度分析
1. 单层循环
例题1（2011年统考真题）
x=2;
while(x < n/2)
x = 2*x;
解析：
-
基本操作：
x=2*x，每次执行后x呈指数增长。 -
执行次数：设循环执行次数为
t，则终止条件为2^(t+1) < n/2，解得t ≈ log₂n - 2。 -
时间复杂度：
O(log₂n)
例题2（立方根循环）
int i=0;
while(i*i*i <= n) i++;
解析：
-
基本操作：
i++，循环终止条件为i³ > n。 -
执行次数：
i的最大值为n^(1/3)。 -
时间复杂度：
O(n^(1/3))
2. 嵌套循环
例题3（2014年统考真题）
count=0;
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
count++;
解析：
-
外层循环次数：
k每次乘以2，执行次数为log₂n。 -
内层循环次数：固定执行
n次。 -
总频次：
n * log₂n，时间复杂度为O(n log n)
例题4（等比数列循环）
int sum=0;
for(int i=1; i<n; i*=2)
for(int j=0; j<i; j++)
sum++;
解析：
-
外层循环次数：
i取值为1, 2, 4, ..., 2^t，次数为log₂n。 -
内层循环总频次：
1 + 2 + 4 + ... + 2^(log₂n) = 2n - 1。 -
时间复杂度：
O(n)
二、递归类时间复杂度分析
例题5（2012年统考真题）
int fact(int n){
if(n<=1) return 1;
return n * fact(n-1);
}
解析：
-
递归深度：递归调用次数为
n次，每次操作为常数时间。 -
时间复杂度：
O(n)
三、链表操作类时间复杂度
例题6（2013年统考真题）
题目：合并两个升序链表为降序链表，最坏时间复杂度。
解析：
-
比较次数：每次比较确定一个元素位置，最坏需比较
m+n次。 -
优化分析：由于每次比较可确定一个元素，实际复杂度为
O(max(m,n))
四、特殊循环条件类
例题7（2019年真题变体）
X=0;
while(N >= X*X + X + 1)
X++;
解析：
-
终止条件：
X² + X + 1 > N，近似解为X ≈ √N。 -
时间复杂度：
O(√N)
五、排序算法复杂度对比
常见排序算法时间复杂度总结
| 算法 | 平均时间复杂度 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 注：稳定性指相等元素的相对顺序是否改变 |
六、易错点总结
-
循环变量非线性增长：如
i *= 2或i = i^3，需通过解不等式确定次数。 -
递归调用次数：递归深度与每层操作数的乘积决定总复杂度。
-
嵌套循环独立性：若内外层循环变量无关，直接相乘；若相关（如内层循环依赖外层变量），需求和计算总频次。