在数据结构的绪论中，时间复杂度和空间复杂度是两个非常重要的概念，它们是衡量算法性能的关键指标。下面是详细讲解：
一、时间复杂度（Time Complexity）
1. 定义
时间复杂度是指算法执行所需要的基本操作次数（如比较、赋值等），通常用大O符号表示，如 O(1)、O(n)、O(n²) 等。
2. 常见时间复杂度（按效率从高到低）
| 时间复杂度 | 描述 | 举例 |
|---|---|---|
| O(1) | 常数时间 | 访问数组元素 |
| O(log n) | 对数时间 | 二分查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序 |
| O(n²) | 二次时间 | 冒泡排序、选择排序 |
| O(2ⁿ) | 指数时间 | 斐波那契递归 |
| O(n!) | 阶乘时间 | 全排列问题 |
3. 计算方法
- 只关注最高阶项（忽略常数、低阶项）
例：T(n) = 3n² + 5n + 2→ 时间复杂度为O(n²) - 循环嵌套法则：嵌套循环时间复杂度相乘
例：两层嵌套循环 →O(n²)
二、空间复杂度（Space Complexity）
1. 定义
空间复杂度是指算法在运行过程中临时占用的存储空间大小，也使用大O表示。
2. 举例说明
- 使用一个固定大小的变量：
O(1) - 使用一个长度为n的数组：
O(n) - 递归调用栈深度为n：
O(n)
3. 空间与时间的权衡
有时为了提高运行速度，可以增加空间（如用哈希表代替遍历），这就是时间换空间，反之亦然。
三、常见例子分析
例1：数组求和
int sum = 0;
for(int i = 0; i < n; i++) {
sum += a[i];
}
- 时间复杂度：
O(n)（遍历n次） - 空间复杂度：
O(1)（只用一个sum变量）
例2：递归求斐波那契数列
int fib(int n) {
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
- 时间复杂度：
O(2ⁿ)（树形递归） - 空间复杂度：
O(n)（递归深度）
四、总结口诀
- 看循环数，判时间复杂度
- 有递归，拆树看规模
- 记住常用复杂度排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
发表回复