复杂度分析：算法的度量衡

写代码这么多年，我越来越觉得，不会分析复杂度的程序员，就像不带地图的探险家。你可能会写出能跑的代码，但很难保证它在真实场景下还能跑得动。

这一章，我们来聊聊复杂度分析。说白了，就是给算法的效率打分。两个维度：时间和空间。

大O表示法：别纠结细节，看趋势

大O表示法，听起来挺唬人。其实核心就一句话：忽略常数，关注增长趋势。

举个例子。你写了个循环，执行了 3n + 5 次操作。用大O表示，就是 O(n)。为什么？因为当 n 足够大时，常数 3 和 5 的影响微乎其微。我们关心的是：当数据量翻倍时，执行时间会怎么变。

常见复杂度：从快到慢排个队

我习惯把常见复杂度排个序，方便对比。下面这张表，建议你记在心里。

复杂度	名称	通俗理解	典型场景
O(1)	常数时间	不管数据多大，时间都一样	数组随机访问、哈希表查找
O(log n)	对数时间	数据翻倍，时间只增加一点点	二分查找、平衡二叉树
O(n)	线性时间	数据翻倍，时间也翻倍	单层循环、遍历数组
O(n log n)	线性对数时间	比线性稍慢，但能接受	归并排序、快速排序（平均）
O(n²)	平方时间	数据翻倍，时间变成4倍	双层循环、冒泡排序
O(2ⁿ)	指数时间	数据稍微增加，时间爆炸	递归斐波那契、穷举

逐项拆解：每个复杂度都值得深挖

O(1) —— 最快的男人

常数时间，意味着执行时间与输入规模无关。数组按下标取值，就是典型的 O(1)。

// 无论数组多大，这条语句都是瞬间完成
int value = arr[100];

哈希表的查找，平均也是 O(1)。但要注意，哈希冲突会让它退化。我曾经在项目中遇到过，因为哈希函数写得不好，导致线上服务响应时间飙升。排查了半天，才发现是哈希表退化成了链表。

O(log n) —— 低调的王者

对数时间，是优化算法时最想达到的目标之一。二分查找就是最好的例子。

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;
}

为什么 O(log n) 这么厉害？因为每次操作，数据量都减半。1000 个数据，最多查 10 次。100 万个数据，最多查 20 次。增长极其缓慢。

O(n) —— 最实在的复杂度

线性时间，就是遍历一遍。大部分“读一遍数据”的操作，都是 O(n)。

// 找最大值，必须看每个元素一眼
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;
}

O(n) 通常是可以接受的。但如果你的代码里出现了多个 O(n) 循环嵌套，就要小心了。

O(n²) —— 性能杀手

平方时间，是新手最容易写出来的复杂度。双层循环，就是它的温床。

// 冒泡排序，经典 O(n²)
void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
            }
        }
    }
}

当 n=1000 时，O(n²) 需要执行 100 万次。当 n=10000 时，就是 1 亿次。性能会急剧下降。

空间换时间：用内存买性能

这是优化领域最经典的思想。说白了就是：如果时间不够，就用空间来凑。

最常见的例子：缓存。把计算结果存起来，下次直接用，省去重复计算的时间。

// 没有缓存：每次都要递归计算
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // O(2ⁿ)
}

// 有缓存：用数组记录中间结果
int fibWithCache(int n, int[] cache) {
    if (n <= 1) return n;
    if (cache[n] != 0) return cache[n];
    cache[n] = fibWithCache(n - 1, cache) + fibWithCache(n - 2, cache);
    return cache[n];  // O(n)
}

你看，用了一个数组（空间），就把指数级的时间降到了线性。这笔买卖，太划算了。

另一个经典例子是哈希表代替循环查找。比如，你要判断一个元素是否在数组中。遍历查找是 O(n)，用哈希表就是 O(1)。代价就是多占一点内存。

知识体系：一张图看懂复杂度

下面这张 SVG 图，把本章的核心知识点串了起来。你可以把它当作思维导图来用。

如何分析一段代码的复杂度？

我总结了一个三步法，分享给你。

1. 找循环：看代码里有几层循环。一层是 O(n)，两层是 O(n²)，以此类推。
2. 找递归：看递归函数调用了自己几次。一次是 O(log n) 或 O(n)，两次以上要小心指数爆炸。
3. 找操作：看循环体里做了什么。如果是 O(1) 的操作，复杂度就是循环层数。如果循环体里还有哈希表查找，要叠加。

写在最后

复杂度分析，是优化能力的地基。你想想看，如果你连代码是快是慢都说不清楚，怎么去优化它？

这一章的内容，说白了就是两件事：看懂大O，学会空间换时间。把这两点吃透，后面的优化技巧才能派上用场。