二、算法复杂度分析：时间复杂度和空间复杂度的概念、大O记号、常见复杂度级别、最坏/平均/最好情况分析、复杂度计算实例

算法复杂度分析是数据结构与算法课程的第一块基石，也是考研笔试与面试中几乎必考的核心能力。它的本质是回答两个问题：当输入规模 n 增大时，程序运行时间增长多快？内存占用增长多快？ 复杂度分析不依赖具体机器、编程语言或编译器，而是从“操作次数”和“存储单元数”的抽象视角衡量算法效率。本章将系统讲解时间/空间复杂度的概念、大O记号的严格定义、常见复杂度级别、三种情况分析以及手算复杂度的标准流程。

2.1 时间复杂度与空间复杂度的核心概念

时间复杂度不是指程序实际运行的秒数，而是指基本操作（赋值、比较、算术运算、数组访问等）的执行次数随输入规模 n 增长的变化趋势。记作 T(n)。空间复杂度则指算法在运行过程中额外占用的存储单元数量随 n 增长的变化趋势，记作 S(n)。这里“额外”二字很关键——输入数据本身占用的空间通常不计入，只统计算法运行所需的辅助空间（如临时变量、数组、递归调用栈等）。

2.2 大O记号：渐进上界的数学定义

大O记号（Big-O Notation）用于描述算法运行时间的渐进上界。严格定义如下：

若存在正常数 c 和 n₀，使得对所有 n ≥ n₀，都有：
    T(n) ≤ c · f(n)
则记作 T(n) = O(f(n))

通俗理解：当 n 足够大时，T(n) 的增长速度不会超过 f(n) 的常数倍。大O记号给出了算法在最坏情况下的“天花板”。除了大O，考研中还可能涉及 Ω（渐进下界）和 Θ（渐进紧确界），但大O是使用最频繁的记号。

2.3 常见复杂度级别与性能对比

考研要求熟练掌握以下复杂度级别，并能按增长速度排序：

2.4 最坏、平均与最好情况分析

同一算法在不同输入下可能表现出不同的时间复杂度。以顺序查找为例：

• 最好情况：目标元素恰好是第一个，只需比较 1 次，T(n) = O(1)。
• 最坏情况：目标元素是最后一个或不存在，需要比较 n 次，T(n) = O(n)。
• 平均情况：假设目标元素出现在任意位置的概率相等，平均比较次数为 (n+1)/2，T(n) = O(n)。

考研中，若无特殊说明，“时间复杂度”默认指最坏时间复杂度。因为最坏情况给出了算法性能的保证上限，是工程中最关心的指标。平均情况分析通常需要假设输入的概率分布，数学上更复杂，但有时能更真实地反映算法性能（如快速排序的平均复杂度为 O(n log n)，但最坏为 O(n²)）。

2.5 复杂度计算实例：从代码到T(n)再到O

下面通过三个典型实例，演示复杂度计算的标准流程。

实例一：单层循环

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;   // 基本操作
}

分析：循环体执行 n 次，每次执行 1 次加法。T(n) = n，时间复杂度为 O(n)。空间上只用了常数个变量，S(n) = O(1)。

实例二：双层嵌套循环

int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;   // 基本操作
    }
}

分析：外层循环 n 次，内层循环每次执行 n 次，总执行次数为 n × n = n²。T(n) = n²，时间复杂度为 O(n²)。若内层循环条件改为 j < i，则总次数为 1+2+...+n = n(n+1)/2，仍为 O(n²)。

实例三：递归算法（斐波那契数列）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

分析：设 T(n) 为计算 fib(n) 的时间。T(n) = T(n-1) + T(n-2) + O(1)。展开可得 T(n) ≈ 2ⁿ，时间复杂度为 O(2ⁿ)。空间复杂度方面，递归深度最大为 n，因此 S(n) = O(n)（递归栈空间）。

2.6 案例拆解：二分查找的复杂度全分析

二分查找是考研最经典的复杂度分析案例。给定一个长度为 n 的有序数组，查找目标值 target。

int binarySearch(int[] arr, int n, int target) {
    int left = 0, right = n - 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 = 10000，target 为数组中间值（最好情况）、数组末尾值（最坏情况）、随机位置（平均情况）。

分析过程：每次循环将搜索区间缩小一半。设循环次数为 k，则经过 k 次后区间长度为 n/2ᵏ。当 n/2ᵏ < 1 时循环结束，即 2ᵏ > n，解得 k > log₂n。因此：

• 最好情况：第一次比较就命中，T(n) = O(1)。
• 最坏情况：直到区间缩为 1 才找到或确认不存在，T(n) = O(log₂n)。
• 平均情况：同样为 O(log₂n)。

空间复杂度：只用了 left、right、mid 三个变量，S(n) = O(1)。

结果对比：若用顺序查找，最坏需要 10000 次比较；二分查找最坏只需 ⌈log₂10000⌉ ≈ 14 次比较。当 n 从 10000 增至 1000000 时，顺序查找时间增长 100 倍，而二分查找仅从 14 次增至 20 次。

风险与代价：二分查找的前提是数组有序，排序本身需要 O(n log n) 的时间。如果数据频繁插入删除，维护有序性的成本可能超过查找收益。因此二分查找适合“静态数据、多次查询”的场景。

复盘经验：分析复杂度时，先判断基本操作是什么，再分析循环/递归的执行次数，最后用大O化简。对于 while 循环，重点观察循环变量每次的变化幅度（倍增、减半、加一），这直接决定了复杂度级别。

2.7 常见误区与总结复盘