Java数据结构 时间复杂度和空间复杂度
在计算机科学中，算法的效率是非常重要的考量因素。算法效率通常分为两类：
- 时间复杂度：衡量算法执行的速度。
- 空间复杂度：衡量算法在执行过程中占用的内存空间。
我们通过数学方式来估算算法的性能，不需要每次都实际运行算法，而是通过复杂度分析方法来衡量效率。下面我们详细讲解时间复杂度和空间复杂度的概念及计算方法。
目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度的概念
2.2 大 O 表示法
2.3 时间复杂度的推导规则
2.4 时间复杂度计算举例
3. 空间复杂度
3.1 空间复杂度的概念
3.2 空间复杂度计算规则
3.3 空间复杂度计算举例
4. 常见时间复杂度和空间复杂度的实例分析
实例 1：常数时间与常数空间
实例 2：线性时间与线性空间
实例 3：递归的时间和空间复杂度
5. 总结
1. 算法效率
算法效率衡量的是算法在时间和空间上的表现。高效的算法应该尽可能减少运行时间（即时间复杂度低）和占用空间（即空间复杂度低）。在实际应用中，我们更关注时间复杂度，但在一些对内存要求高的场景下，空间复杂度也非常重要。
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度衡量的是算法执行所需要的时间，通常以基本操作的次数来表示。基本操作通常是算法中最耗时的部分，例如数组的访问、赋值、比较等。
2.2 大 O 表示法
为了量化算法的执行时间，我们使用大 O 表示法（Big-O Notation），它表示算法在输入规模较大时的增长趋势。大 O 表示的是时间复杂度的上界，通常我们关注的是算法的最坏情况。
常见的时间复杂度类型（按增长速度从慢到快排列）：
- O(1)：常数时间复杂度。算法的执行时间与输入无关，始终是常数。
- O(log N)：对数时间复杂度。每次操作能将问题规模减少一半，如二分查找。
- O(N)：线性时间复杂度。算法的执行时间与输入规模成正比，如遍历数组。
- O(N log N)：线性对数时间复杂度。通常出现在高效排序算法中，如归并排序。
- O(N²)：平方时间复杂度。通常出现在嵌套循环中，如冒泡排序。
- O(2^N)：指数时间复杂度。通常出现在递归问题中，如斐波那契数列的递归求解。
2.3 时间复杂度的推导规则
- 只保留最高量级：忽略常数项和低阶项。例如，若算法的时间复杂度是
5N^2 + 3N + 2，最终时间复杂度为 O(N²)。 - 忽略常数系数：时间复杂度表示的是增长趋势，常数因子不影响复杂度的阶。例如，
3N和100N的时间复杂度都是 O(N)。 - 嵌套循环：时间复杂度是内外层循环的乘积。例如，双重嵌套的循环每个循环遍历
N次，时间复杂度为 O(N²)。
2.4 时间复杂度计算举例
示例 1：单次遍历数组
for (int i = 0; i < N; i++) {// 常数时间操作
}
时间复杂度：O(N)，因为循环执行了 N 次。
示例 2：双重嵌套循环
for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {// 常数时间操作}
}
时间复杂度：O(N²)，因为外层循环和内层循环的执行次数分别是 N，总共执行了 N*N 次。
示例 3：二分查找
while (low <= high) {int mid = (low + high) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {low = mid + 1;} else {high = mid - 1;}
}
时间复杂度：O(log N)，每次查找能将搜索空间减半。
3. 空间复杂度
3.1 空间复杂度的概念
空间复杂度衡量的是算法在运行过程中所需要的额外空间。空间复杂度不计算输入数据本身所占用的空间，而是计算算法执行过程中额外分配的空间大小。
常见的空间复杂度：
- O(1)：常数空间。算法仅使用了固定的空间。
- O(N)：线性空间。算法使用的空间与输入规模成正比。
3.2 空间复杂度计算规则
空间复杂度的计算规则与时间复杂度类似，主要关注的是数据结构和递归调用的空间占用情况。
- 如果算法只用了常数个额外变量，那么空间复杂度是 O(1)。
- 如果算法用了一个长度为
N的数组，或者在递归过程中每次递归都会增加栈的深度，空间复杂度就是 O(N)。
3.3 空间复杂度计算举例
示例 1：只使用了常数个额外空间
int sum = 0;
for (int i = 0; i < N; i++) {sum += i;
}
空间复杂度：O(1)，因为只用了固定数量的变量，空间使用量不随输入规模变化。
示例 2：使用了额外的数组
int[] arr = new int[N];
for (int i = 0; i < N; i++) {arr[i] = i;
}
空间复杂度：O(N)，因为创建了长度为 N 的数组。
示例 3：递归调用
public int factorial(int n) {if (n == 1) {return 1;}return n * factorial(n - 1);
}
空间复杂度：O(N)，因为递归调用的深度是 N，每次递归调用都需要在栈上开辟新的栈帧。
4. 常见时间复杂度和空间复杂度的实例分析
实例 1：常数时间与常数空间
int add(int a, int b) {return a + b;
}
- 时间复杂度：O(1)，因为只执行了常数时间操作。
- 空间复杂度：O(1)，因为只使用了常数个变量。
实例 2：线性时间与线性空间
int[] doubleArray(int[] arr) {int[] result = new int[arr.length];for (int i = 0; i < arr.length; i++) {result[i] = arr[i] * 2;}return result;
}
- 时间复杂度：O(N)，因为遍历了整个数组，执行了
N次操作。 - 空间复杂度：O(N)，因为创建了一个新的与输入数组大小相同的数组。
实例 3：递归的时间和空间复杂度
int fib(int n) {if (n <= 1) {return n;}return fib(n - 1) + fib(n - 2);
}
- 时间复杂度：O(2^N)，因为每次递归会进行两次递归调用，导致指数级增长。
- 空间复杂度：O(N)，因为递归调用的最大深度为
N，每次递归都需要栈空间。
5. 总结
-
时间复杂度：衡量的是算法的运行时间，通常使用大 O 表示法，常见的时间复杂度有 O(1)、O(N)、O(N²) 和 O(log N) 等。
-
空间复杂度：衡量的是算法所占用的内存空间，计算的是额外的存储需求，也使用大 O 表示法。
-
计算规则：
- 时间复杂度：关注循环次数、递归深度等。
- 空间复杂度：关注变量和递归栈帧的占用。
-
实例分析：
- 常数时间和常数空间的算法是最优的（如 O(1)）。
- 线性时间复杂度算法（如 O(N)）适合处理较大规模的数据。
- 嵌套循环可能会导致平方时间复杂度（如 O(N²)），需要尽量避免。
通过理解时间和空间复杂度，可以在设计和选择算法时做出更合理的决策，从而提高程序的性能。