常见复杂度对比与选择 ​

前两章我们学习了时间复杂度和空间复杂度的分析方法。但在实际刷题和工作中，一个关键问题是：面对不同的数据规模，我应该选择什么复杂度的算法？

这一章，我们来建立复杂度与实际性能之间的直觉。

复杂度的直观理解 ​

O(n²) 比 O(n) 慢，这谁都知道。但慢多少？

让我们用具体数字来感受一下：

看到了吗？

当 n = 10⁶ 时：

• O(n) 做 100 万次操作——没问题
• O(n²) 做 1 万亿次操作——基本上要跑几个小时
• O(2^n)——宇宙毁灭都算不完

这就是为什么复杂度分析如此重要。选错算法，差的不是几倍，而是几个数量级。

复杂度与运行时间的关系 ​

有一条经验法则：现代计算机每秒大约能执行 10⁸ ~ 10⁹ 次基本操作。

LeetCode 题目通常有 1~2 秒的时间限制。结合这两点，我们可以推算出：对于给定的数据规模 n，算法的复杂度上限是多少。

这张表非常实用。

当你看到一道 LeetCode 题，先看数据范围：

• 如果 n ≤ 1000，暴力 O(n²) 通常能过
• 如果 n ≤ 10⁵，你需要想一个 O(n log n) 或 O(n) 的算法
• 如果 n ≤ 10⁷，只能用 O(n) 了
• 如果 n > 10⁸，通常需要数学技巧或预计算

当然，这只是经验法则，不是绝对标准。常数因子、缓存命中率、实际操作的复杂程度都会影响实际运行时间。但作为快速判断，这张表够用了。

复杂度选择的实际案例 ​

让我们用一个具体例子来说明：在数组中查找目标值。

方法 1：线性查找 ​

// 时间 O(n)，空间 O(1)
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

从头到尾扫一遍。简单直接，没有前提条件。

方法 2：二分查找 ​

// 时间 O(log n)，空间 O(1)
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

每次砍掉一半。但有一个前提：数组必须有序。

方法 3：哈希表查找 ​

// 预处理时间 O(n)，单次查询 O(1)
function createIndex(arr) {
    const map = new Map();
    for (let i = 0; i < arr.length; i++) {
        map.set(arr[i], i);
    }
    return map;
}

function hashSearch(map, target) {
    return map.has(target) ? map.get(target) : -1;
}

用空间换时间。先花 O(n) 建立索引，之后每次查询都是 O(1)。

如何选择？ ​

选择的关键不是"哪个最快"，而是"哪个最适合当前场景"。

如果数组很小（几十个元素），线性查找简单可靠，没必要用哈希表。

如果数据已经排好序，二分查找是最佳选择——O(log n) 且不需要额外空间。

如果需要对同一个数组进行成千上万次查询，先花 O(n) 建哈希表是值得的。

最坏、平均、最好情况 ​

同一个算法，在不同输入下可能表现差异很大。

三种情况 ​

• 最好情况（Best Case）：最有利输入下的复杂度
• 平均情况（Average Case）：所有输入的期望复杂度
• 最坏情况（Worst Case）：最不利输入下的复杂度

例子：快速排序 ​

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[0];  // 选第一个元素作为基准
    const left = arr.slice(1).filter(x => x < pivot);
    const right = arr.slice(1).filter(x => x >= pivot);
    
    return [...quickSort(left), pivot, ...quickSort(right)];
}

快排的复杂度取决于 pivot 选得好不好：

• 最好情况：每次 pivot 都是中位数，数组均匀分成两半 → O(n log n)
• 平均情况：随机输入 → O(n log n)
• 最坏情况：数组已排序，每次 pivot 都是最小/最大值 → O(n²)

我们关注哪个？ ​

通常关注最坏情况，因为：

1. 它代表了算法的"底线"
2. 在实际应用中，我们不想依赖运气
3. 面试和竞赛中，测试用例往往会故意构造最坏情况

但平均情况也很重要。快速排序虽然最坏是 O(n²)，但因为平均情况是 O(n log n)，而且常数因子小，实际中仍然是最快的排序算法之一。

如何根据题目选择算法 ​

分享一个实用的决策流程：

第一步：看数据规模

题目会给出数据范围，比如 1 ≤ n ≤ 10⁵。

根据前面的表格，10⁵ 意味着你需要 O(n log n) 或更优的算法。O(n²) 大概率超时。

第二步：考虑数据特征

• 数据有序吗？→ 考虑二分
• 需要查找吗？→ 考虑哈希表
• 有重复子问题吗？→ 考虑动态规划
• 需要枚举所有可能吗？→ 考虑回溯

第三步：从简单开始

如果数据规模允许，先写暴力解法。它能帮你理解问题，也能作为优化解法的对照。

很多时候，暴力解法通过一点优化（比如剪枝、记忆化）就能达到要求。

第四步：识别瓶颈

如果暴力解法超时，分析它慢在哪里：

• 是重复计算了？→ 加缓存
• 是遍历次数太多？→ 换数据结构
• 是排序太慢？→ 考虑能否避免排序

本章小结 ​

本章的核心是建立复杂度与实际性能的直觉：

1. 数量级差异：O(n) 和 O(n²) 在大数据下差的是万亿倍，不是几倍
2. 经验法则：10⁸ 次/秒，1~2 秒限制，据此推算可接受的复杂度
3. 场景适配：没有"最好的算法"，只有"最适合的算法"
4. 关注最坏情况：但也要理解平均情况的价值
5. 从数据规模出发：看到题目先看 n，再选算法

建立这种直觉需要练习。刷题时，养成先看数据范围的习惯。慢慢地，你会形成条件反射：看到 n ≤ 10⁵，脑子里自动浮现 O(n log n)。

下一章，我们来分析一类特殊情况——递归与迭代的复杂度分析。