时间复杂度
时间复杂度
一、为什么需要时间复杂度？
在编程中，同一个问题可以有多种不同的解法。时间复杂度帮助我们：
- 比较算法效率：判断哪个算法更快
- 预测性能表现：当数据量增大时，算法会变慢多少
- 优化代码：找出程序中的性能瓶颈
📊 不同算法处理不同规模数据的耗时对比：
数据规模(n) O(1) O(log n) O(n) O(n²) O(2ⁿ) 10 1ms 1ms 1ms 1ms 1ms 100 1ms 2ms 10ms 100ms 10¹³年 1000 1ms 3ms 100ms 10秒 - 10000 1ms 4ms 1秒 100秒 -
二、时间复杂度是什么？
时间复杂度描述算法运行时间如何随输入规模(n) 增长而变化。我们使用大O符号(O) 表示。
核心概念：
- 关注增长趋势，忽略常数项
- 关注最坏情况下的表现
- 忽略低阶项，只保留最高阶项
三、常见时间复杂度详解（C++示例）
1. O(1) - 常数时间
无论输入多大，执行时间不变
#include <iostream>
using namespace std;
int constant_time(int n) {
// 以下操作只执行一次
int a = n * 10;
int b = n / 2;
return a + b;
}
int main() {
cout << constant_time(100); // 无论n多大，操作次数相同
return 0;
}
操作次数：固定次数（与n无关）
时间复杂度：O(1)
2. O(n) - 线性时间
执行时间与输入规模n成正比
#include <iostream>
using namespace std;
int linear_time(int n) {
int total = 0;
// 循环n次
for (int i = 0; i < n; i++) {
total += i; // 每次循环执行1次操作
}
return total;
}
int main() {
cout << linear_time(100); // n=100，执行100次加法
return 0;
}
操作次数：n次
时间复杂度：O(n)
3. O(n²) - 平方时间
常见于嵌套循环
#include <iostream>
using namespace std;
int quadratic_time(int n) {
int count = 0;
// 外层循环n次
for (int i = 0; i < n; i++) {
// 内层循环n次
for (int j = 0; j < n; j++) {
count++; // 执行n*n次
}
}
return count;
}
int main() {
cout << quadratic_time(10); // n=10，执行100次
return 0;
}
操作次数：n * n = n²
时间复杂度：O(n²)
4. O(log n) - 对数时间
每次操作将问题规模减半
#include <iostream>
using namespace std;
int logarithmic_time(int n) {
int count = 0;
// 每次循环i减半
for (int i = n; i > 1; i /= 2) {
count++;
}
return count;
}
int main() {
cout << logarithmic_time(1024); // log₂(1024)=10
return 0;
}
操作次数：log₂(n)
时间复杂度：O(log n)
5. O(n log n) - 线性对数时间
高效排序算法的时间复杂度
#include <iostream>
using namespace std;
int linear_log_time(int n) {
int count = 0;
// 外层循环：O(n)
for (int i = 0; i < n; i++) {
// 内层循环：O(log n)
for (int j = n; j > 1; j /= 2) {
count++;
}
}
return count;
}
int main() {
cout << linear_log_time(10); // 10 * log₂(10) ≈ 33
return 0;
}
操作次数：n * log n
时间复杂度：O(n log n)
四、时间复杂度对比图
📈 时间复杂度增长曲线图：
五、如何分析时间复杂度？
1. 循环分析法则
- 单层循环：循环次数 × 循环体内操作
- 嵌套循环：各层循环次数的乘积
- 并列循环：取最大值
2. 示例分析
#include <iostream>
using namespace std;
int example(int n) {
int sum = 0;
// O(n)
for (int i = 0; i < n; i++) {
sum += i;
}
// O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum += i * j;
}
}
// O(1)
return sum;
}
总时间复杂度 = O(n) + O(n²) + O(1) = O(n²)
六、递归算法的时间复杂度
递归时间复杂度 = 递归调用次数 × 每次调用的时间复杂度
示例：斐波那契数列（低效版）
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
int main() {
cout << fibonacci(10); // 时间复杂度O(2ⁿ)
return 0;
}
时间复杂度分析：
递归树高度：n
每个节点分支：2
总操作数：约2ⁿ
时间复杂度：O(2ⁿ)
七、常见算法的时间复杂度
| 算法 | 最优 | 平均 | 最差 | 说明 |
|---|---|---|---|---|
| 线性查找 | O(1) | O(n) | O(n) | 简单查找 |
| 二分查找 | O(1) | O(log n) | O(log n) | 要求有序数组 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | 简单排序 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 常用高效排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | 稳定排序 |
| 选择排序 | O(n²) | O(n²) | O(n²) | 每次选最小元素 |
八、练习与答案（C++代码）
练习1：分析时间复杂度
int func1(int n) {
int total = 0;
for (int i = 0; i < 5; i++) {
total += i;
}
for (int j = 0; j < n; j++) {
total += j;
}
for (int k = 0; k < 2 * n; k++) {
total += k;
}
return total;
}
练习2：分析时间复杂度
int func2(int n) {
int count = 0;
int i = 1;
while (i < n) {
count++;
i *= 2;
}
return count;
}
练习3：分析时间复杂度
int func3(int n) {
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1000; j++) {
total += j;
}
}
return total;
}
参考答案：
- O(5) + O(n) + O(2n) = O(n)
- 循环次数 = log₂(n)，时间复杂度 O(log n)
- O(n × 1000) = O(n)
* 保留T(n)的最高次项且去掉其系数
九、总结
- ⚡ O(1)、O(log n)、O(n)：高效算法，可处理大规模数据
- ⏳ O(n log n)：大多数高效排序算法的时间复杂度
- 🐢 O(n²)、O(2ⁿ)、O(n!)：低效算法，仅适用于小规模数据
C++编程建议：
- 使用STL容器：
vector/unordered_map等优化时间复杂度- 避免深层嵌套循环：尝试优化为O(n log n)或更好
- 递归算法考虑使用记忆化（memoization）优化
- 对于大规模数据，O(n²)算法通常是不可接受的
- 使用
<algorithm>中的高效算法（如sort是O(n log n)）
理解时间复杂度是成为优秀C++程序员的关键一步！多加练习，你会越 来越熟练地分析代码性能！💪