算法复杂度分析与大O表示法

一、为什么需要复杂度分析

1.1 事后统计法的局限

• 依赖测试环境（CPU、内存、操作系统）
• 依赖测试数据规模
• 无法提前预估算法性能

1.2 复杂度分析的优势

• 不依赖具体环境
• 反映算法随数据规模增长的趋势
• 可以在编码阶段预估性能

二、大O表示法

2.1 定义

大O表示法描述算法执行时间（或占用空间）随输入规模增长的变化趋势：
[ T(n) = O(f(n)) ]

表示存在常数 ( c ) 和 ( n_0 )，使得当 ( n \geq n_0 ) 时，( T(n) \leq c \cdot f(n) )。

2.2 核心原则

1. 只关注最高阶项：( O(2n^2 + 3n + 1) = O(n^2) )
2. 忽略常数系数：( O(3n) = O(n) )
3. 关注最坏情况：通常分析上界

三、常见时间复杂度

复杂度	名称	示例
( O(1) )	常数阶	数组随机访问
( O(\log n) )	对数阶	二分查找
( O(n) )	线性阶	遍历数组
( O(n\log n) )	线性对数阶	快速排序平均
( O(n^2) )	平方阶	冒泡排序
( O(n^3) )	立方阶	三层嵌套循环
( O(2^n) )	指数阶	斐波那契递归
( O(n!) )	阶乘阶	全排列

3.1 复杂度曲线对比

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

当 ( n = 1000 ) 时：

• ( O(1) ): 1
• ( O(\log n) ): ~10
• ( O(n) ): 1000
• ( O(n^2) ): 1,000,000
• ( O(2^n) ): 无法计算

四、时间复杂度分析实例

4.1 单层循环

// O(n)
for (int i = 0; i < n; i++) {
    System.out.println(i);
}

4.2 嵌套循环

// O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 操作
    }
}

4.3 对数级循环

// O(log n)
for (int i = 1; i < n; i *= 2) {
    // 操作
}

4.4 递归算法 - 斐波那契

// O(2ⁿ) - 存在大量重复计算
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

递归树有 ( 2^n ) 个节点，但存在大量重叠子问题。

4.5 递归算法 - 归并排序

// O(n log n)
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)
        merge(arr, left, mid, right);   // O(n)
    }
}

递推公式：( T(n) = 2T(n/2) + O(n) )
由主定理可得 ( T(n) = O(n \log n) )

五、空间复杂度

5.1 定义

算法执行过程中临时占用存储空间大小的量度。

5.2 常见空间复杂度

• ( O(1) ): 仅使用常数额外空间
• ( O(n) ): 使用与输入规模成正比的额外空间
• ( O(n^2) ): 二维数组等
• ( O(\log n) ): 递归调用栈深度

5.3 实例分析

// 空间复杂度 O(1)
int sum(int[] arr) {
    int result = 0;  // 常量空间
    for (int num : arr) {
        result += num;
    }
    return result;
}

// 空间复杂度 O(n)
int[] copy(int[] arr) {
    int[] result = new int[arr.length];  // 与输入规模成正比
    System.arraycopy(arr, 0, result, 0, arr.length);
    return result;
}

// 空间复杂度 O(log n) - 递归栈
int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    }
    return binarySearch(arr, target, mid + 1, right);
}

六、最好、最坏、平均情况

情况	说明	示例
最好	最理想输入	查找第一个元素就是目标
最坏	最不利输入	查找最后一个或不存在
平均	随机输入的期望	概率加权平均值
均摊	一系列操作的平均	动态数组扩容

通常关注最坏情况复杂度，因为它给出了性能上界。

七、均摊复杂度

7.1 动态数组扩容

// ArrayList的add操作
// 大部分情况O(1)，扩容时O(n)
// 均摊复杂度为O(1)

7.2 分析方法

将昂贵操作的成本均摊到多次廉价操作上。如果每 ( n ) 次操作触发一次 ( O(n) ) 操作，则均摊为 ( O(1) )。

八、复杂度分析常见误区

1. 忽略常数时间的隐性成本：缓存不命中、内存分配
2. 只看时间忽略空间：有时空间换时间是值得的
3. 理论 vs 实际：大O忽略常数，实际中小数据量可能 ( O(n^2) ) 更快
4. 递归只算调用次数：要算上每次调用的工作量

九、总结

复杂度分析是评估算法效率的核心工具。掌握大O表示法，能够在编码前预判算法性能，做出合理的实现选择。记住：大O描述的是趋势，不是精确值。