[L1] 算法复杂度分析与 Big-O 表示法

一句话结论

Big-O 描述算法随输入规模增长的性能上界，时间与空间复杂度是核心评价维度。

体系讲解

Big-O 的含义

Big-O 表示算法在最坏情况下，随输入规模 n 增长时所需资源（时间/空间）的增长趋势上界。 它忽略常数系数和低阶项，只关注增长速率——因为 n 足够大时，这些细节对量级判断没有意义。

两条化简规则

1. 去掉常数系数：3n → O(n)，100 → O(1)
2. 保留最高次项：n² + n + 1 → O(n²)

常见复杂度量级（从优到劣）

量级	名称	典型场景
O(1)	常数	数组按索引取值、哈希表查找
O(log n)	对数	二分查找、平衡二叉搜索树
O(n)	线性	单层 for 循环遍历
O(n log n)	线性对数	快速排序（平均）、归并排序
O(n²)	平方	双重嵌套循环、冒泡排序
O(2ⁿ)	指数	无剪枝递归穷举（如幂集）
O(n!)	阶乘	全排列暴力穷举

时间复杂度 vs 空间复杂度

• 时间复杂度：算法执行所需操作次数随 n 的增长趋势
• 空间复杂度：算法执行所需额外内存随 n 的增长趋势（不含输入本身）
  • 迭代算法通常 O(1) 额外空间；递归算法受调用栈深度影响，最坏 O(n)

最坏 / 平均 / 最好情况

情况	含义	示例（快速排序）
最坏（Worst）	输入最不利时的上界，Big-O 默认描述此情形	每次选到最大/最小值作 pivot → O(n²)
平均（Average）	随机输入下的期望值，需概率分析	随机 pivot → O(n log n)
最好（Best）	输入最有利时的下界，实际意义有限	已排序数组 + 三路划分 → O(n)

面试中若无特别说明，复杂度通常指最坏情况。

算法评价标准（不止复杂度）

• 正确性：最基本要求
• 时间复杂度：渐进性能
• 空间复杂度：内存开销
• 稳定性（排序特有）：相等元素相对顺序是否保留
• 实现复杂度：工程可维护性

考察意图

考查候选人是否具备分析代码性能的基本量化能力；区分"感觉慢"与"能说出 O(n²)"的候选人；也是后续所有算法题的前置语言。

追问链

1. 双重嵌套 for 循环一定是 O(n²) 吗？
   简答：不一定。内层循环次数若与外层无关（如固定 26 次字母遍历），整体仍是 O(n)；若内层上界也是 n，才是 O(n²)。判断时需看两层循环变量是否都依赖 n。

2. 递归函数的空间复杂度如何计算？
   简答：递归的空间复杂度主要来自调用栈深度。如 fibonacci(n) 递归深度最大为 n，空间复杂度 O(n)；尾递归优化（PHP 不自动支持）可降到 O(1)。每层栈帧存储局部变量和返回地址。

3. O(n log n) 为什么是"分治"的典型量级？
   简答：分治每次将问题规模减半（产生 log n 层），每层合并操作处理全部 n 个元素——O(n) × O(log n) = O(n log n)。归并排序是最直观的例子。

4. 如何快速推导一段代码的时间复杂度？
   简答：三步法——①找最内层基本操作；②分析执行次数关于 n 的函数；③保留最高次项、去掉常数系数。遇到递归用递推公式（如 T(n) = 2T(n/2) + O(n) → O(n log n)）。

易错点

1. 把"操作次数"当时间复杂度：O(3n+5) 要化简为 O(n)，面试时直接报 "O(3n)" 会显得不熟练；Big-O 只关注量级，常数和低阶项必须去掉。
2. 忽略空间复杂度：只背时间复杂度，忽略递归调用栈或辅助数组的空间开销；面试中追问"有没有 O(1) 空间的解法"时容易答不上来。
3. 默认"最好情况"：认为快速排序是 O(n log n) 因此优于归并排序——实际上快排最坏 O(n²)（已排序数组 + 固定 pivot），归并排序始终 O(n log n)，需结合场景讨论。

代码示例

<?php

// O(1)：常数次操作，与 n 无关
function getFirst(array $arr): mixed
{
    return $arr[0] ?? null;
}

// O(n)：单层遍历
function linearSearch(array $arr, int $target): int
{
    foreach ($arr as $i => $val) {
        if ($val === $target) return $i;
    }
    return -1;
}

// O(n²)：双重嵌套，两层均依赖 n
function hasDuplicate(array $arr): bool
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] === $arr[$j]) return true;
        }
    }
    return false;
}

// O(log n)：每次将搜索范围减半
function binarySearch(array $sorted, int $target): int
{
    [$lo, $hi] = [0, count($sorted) - 1];
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($sorted[$mid] === $target) return $mid;
        $sorted[$mid] < $target ? $lo = $mid + 1 : $hi = $mid - 1;
    }
    return -1;
}