复杂度分析
复杂度分析是评估算法效率的核心方法。理解复杂度分析可以帮助我们选择最优的算法。
时间复杂度
时间复杂度表示算法执行时间与数据规模之间的增长关系。
大 O 表示法
大 O 表示法（Big O Notation）用于描述算法的时间复杂度：
- O 表示"Order of"（数量级）
- 关注的是增长趋势，忽略常数和低阶项
- 表示最坏情况下的时间复杂度
示例：
// O(1) - 常数阶
public int getFirst(int[] arr) {
return arr[0]; // 只执行一次操作
}
// O(n) - 线性阶
public int sum(int[] arr) {
int total = 0;
for (int i = 0; i < arr.length; i++) { // 循环 n 次
total += arr[i];
}
return total;
}
// O(n²) - 平方阶
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) { // 嵌套循环
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
常见时间复杂度
O(1) - 常数阶
无论数据规模多大，执行时间固定：
public int getElement(int[] arr, int index) {
return arr[index]; // 数组随机访问，O(1)
}
public boolean isEven(int n) {
return n % 2 == 0; // 简单计算，O(1)
}
解释：常数阶操作不随输入规模变化。即使有多个操作，如 a = 1; b = 2; c = 3;，仍然是 O(1)。
O(log n) - 对数阶
每次操作使问题规模减半：
// 二分查找
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到
}
解释：二分查找每次将搜索范围缩小一半，n 次操作后范围变为 n/2^n，当范围变为 1 时结束，所以 log₂n 次操作。
O(n) - 线性阶
执行时间与数据规模成正比：
// 查找最大值
public int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) { // 遍历所有元素
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 线性查找
public int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
O(n log n) - 线性对数阶
常见于高效排序算法：
// 归并排序
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 分治
mergeSort(arr, left, mid); // T(n/2)
mergeSort(arr, mid + 1, right); // T(n/2)
// 合并 O(n)
merge(arr, left, mid, right);
}
}
// T(n) = 2T(n/2) + O(n) => O(n log n)
O(n²) - 平方阶
常见于嵌套循环：
// 冒泡排序
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 总次数：(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
O(2ⁿ) - 指数阶
常见于递归问题：
// 斐波那契数列（递归实现）
public int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // 每次调用产生两个分支
}
解释：递归调用形成二叉树结构，节点数约为 2ⁿ。这种实现效率很低，可以使用动态规划优化到 O(n)。
O(n!) - 阶乘阶
常见于全排列问题：
// 全排列
public void permute(int[] arr, int start, List<List<Integer>> result) {
if (start == arr.length - 1) {
List<Integer> permutation = new ArrayList<>();
for (int num : arr) {
permutation.add(num);
}
result.add(permutation);
return;
}
for (int i = start; i < arr.length; i++) {
swap(arr, start, i);
permute(arr, start + 1, result);
swap(arr, start, i); // 回溯
}
}
复杂度比较
从小到大排序：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
可视化对比：
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | O(n!) |
|---|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1024 | 3628800 |
| 100 | 1 | 7 | 100 | 664 | 10000 | 10³⁰ | 10¹⁵⁸ |
| 1000 | 1 | 10 | 1000 | 9966 | 10⁶ | 10³⁰¹ | 极大 |
解释：当 n 较大时，指数阶和阶乘阶的增长速度极其惊人，实际应用中应尽量避免。
空间复杂度
空间复杂度表示算法执行过程中所需的存储空间与数据规模的关系。
O(1) - 常数空间
只使用固定大小的额外空间：
// 交换两个变量
public void swap(int[] arr, int i, int j) {
int temp = arr[i]; // 只使用一个临时变量
arr[i] = arr[j];
arr[j] = temp;
}
O(n) - 线性空间
空间与输入规模成正比：
// 复制数组
public int[] copyArray(int[] arr) {
int[] copy = new int[arr.length]; // 新数组，O(n) 空间
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
return copy;
}
// 递归调用栈
public int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // 递归深度 n，空间 O(n)
}
O(n²) - 平方空间
// 二维数组
public int[][] createMatrix(int n) {
int[][] matrix = new int[n][n]; // n x n 矩阵
return matrix;
}
最好、最坏、平均情况
算法的时间复杂度在不同情况下可能不同：
// 线性查找
public int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
分析：
- 最好情况：目标在第一个位置，O(1)
- 最坏情况：目标不存在或在最后，O(n)
- 平均情况：目标在任意位置的概率相等，O(n/2) = O(n)
通常我们关注最坏情况，因为它给出了算法性能的上界保证。
均摊复杂度
某些操作的大多数情况很快，偶尔很慢，这时使用均摊分析：
// 动态数组扩容
public class DynamicArray {
private int[] data;
private int size;
public void add(int element) {
if (size == data.length) {
resize(); // 扩容 O(n)
}
data[size++] = element; // 添加 O(1)
}
private void resize() {
int[] newData = new int[data.length * 2];
for (int i = 0; i < data.length; i++) {
newData[i] = data[i];
}
data = newData;
}
}
分析：
- 每次 add 操作：O(1)
- 偶尔扩容：O(n)
- 均摊后：每次 add 仍然是 O(1)
解释：假设初始容量为 1，扩容 n 次后容量为 2ⁿ。扩容操作次数为 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1，而添加了 2ⁿ 个元素，均摊每个元素的扩容成本为常数。
递归复杂度分析
主定理
对于递归关系 T(n) = aT(n/b) + f(n)：
- a：递归子问题数量
- b：子问题规模缩小的倍数
- f(n)：递归外的额外工作
三种情况：
- 若 f(n) = O(n^(log_b(a-e)))，则 T(n) = Θ(n^log_b(a))
- 若 f(n) = Θ(n^log_b(a))，则 T(n) = Θ(n^log_b(a) * log n)
- 若 f(n) = Ω(n^(log_b(a+e)))，则 T(n) = Θ(f(n))
示例分析
// 二分查找：T(n) = T(n/2) + O(1)
// a=1, b=2, f(n)=O(1)=O(n^0)
// log_b(a) = log_2(1) = 0
// 情况2：T(n) = O(log n)
// 归并排序：T(n) = 2T(n/2) + O(n)
// a=2, b=2, f(n)=O(n)
// log_b(a) = log_2(2) = 1
// 情况2：T(n) = O(n log n)
// 快速排序（平均）：T(n) = 2T(n/2) + O(n)
// 同样 O(n log n)
复杂度优化技巧
1. 空间换时间
使用额外空间减少时间复杂度：
// 两数之和 - 暴力解法 O(n²)
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
// 优化解法 O(n) - 使用哈希表
public int[] twoSumOptimized(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return null;
}
2. 预处理
提前计算减少重复工作：
// 前缀和 - 区间求和
public class PrefixSum {
private int[] prefix;
public PrefixSum(int[] nums) {
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i]; // 预处理 O(n)
}
}
// 区间 [i, j] 的和，O(1)
public int rangeSum(int i, int j) {
return prefix[j + 1] - prefix[i];
}
}
3. 懒惰求值
只在需要时计算：
// 缓存斐波那契结果
public class Fibonacci {
private static Map<Integer, Long> cache = new HashMap<>();
public static long fib(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) {
return cache.get(n); // 直接返回缓存结果
}
long result = fib(n - 1) + fib(n - 2);
cache.put(n, result); // 缓存结果
return result;
}
}
小结
本章我们学习了：
- 大 O 表示法：描述算法复杂度的标准方法
- 常见时间复杂度：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)
- 空间复杂度：算法所需的存储空间
- 最好、最坏、平均情况：不同情况下的复杂度分析
- 均摊复杂度：处理偶发高成本操作的分析方法
- 主定理：递归算法复杂度的通用公式
练习
-
分析以下代码的时间复杂度：
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j++) {
// O(1) 操作
}
} -
实现一个函数，判断一个数是否为 2 的幂次，要求 O(1) 时间复杂度
-
分析快速排序在最好和最坏情况下的时间复杂度
-
使用主定理分析 T(n) = 3T(n/4) + O(n²) 的复杂度