一、算法复杂度分析：大O表示法、时间复杂度、空间复杂度、最好/最坏/平均情况分析
聊算法，第一个绕不开的就是复杂度分析。
说实话，我刚开始学算法时，觉得这东西挺虚的。不就是数数循环跑了多少次吗？后来在项目中吃了亏，才明白——不懂复杂度，写出来的代码可能就是一颗定时炸弹。
1.1 为什么我们要关心复杂度？
你想想看，同样的功能，你的代码跑 1 秒，别人的跑 1 小时。差别在哪？
不是语法问题，也不是机器配置问题。核心在于——算法选错了。
复杂度分析，就是帮你提前判断：这个算法，到底行不行。
核心观点：复杂度分析不是理论游戏，它是你写出高性能代码的「体检报告」。
1.2 大O表示法——算法的「量级」标签
大O表示法，说白了就是描述算法运行时间随数据规模增长的趋势。
它不关心具体跑了多少毫秒，只关心「当 n 很大时，大概是什么量级」。
举个例子：
// 场景：在数组中查找某个值
// 方式一：遍历查找
function find(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// 时间复杂度：O(n)
// 方式二：二分查找（前提是数组已排序）
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 时间复杂度：O(log n)
看到区别了吗？当 n=100 万时，O(n) 可能要跑 100 万步，而 O(log n) 只需要大约 20 步。这就是量级的碾压。
我的习惯：写代码前，先估算一下数据规模。如果 n 超过 10 万，O(n²) 的算法基本就要慎重了。
1.3 常见时间复杂度速查表
| 大O表示 | 名称 | 典型算法 | n=1000 时的大致操作数 |
|---|---|---|---|
| O(1) | 常数时间 | 数组随机访问、哈希表查找 | 1 |
| O(log n) | 对数时间 | 二分查找、平衡树查找 | 约 10 |
| O(n) | 线性时间 | 数组遍历、链表查找 | 1000 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序（平均） | 约 10000 |
| O(n²) | 平方时间 | 冒泡排序、选择排序 | 1,000,000 |
| O(2ⁿ) | 指数时间 | 递归斐波那契（未优化） | 天文数字 |
我曾经踩过的坑：有一次处理 50 万条数据，用了 O(n²) 的双层循环。本地测试数据少没发现，上线后直接卡死。后来改成 O(n log n) 的方案，问题秒解。所以——数据量一大，复杂度就是生死线。
1.4 时间复杂度分析——三个关键点
分析时间复杂度，我一般看三个地方：
- 循环层数——一层循环通常是 O(n)，两层嵌套就是 O(n²)
- 递归深度——递归调用了多少次？每次调用数据规模减半？那就是 O(log n)
- 核心操作——循环体里有没有更耗时的操作？比如数组插入、字符串拼接
举个例子：
function example(arr) {
let sum = 0; // O(1)
for (let i = 0; i < n; i++) { // 循环 n 次
sum += arr[i]; // O(1)
}
for (let i = 0; i < n; i++) { // 循环 n 次
for (let j = 0; j < n; j++) { // 嵌套循环 n 次
console.log(i, j); // O(1)
}
}
return sum;
}
// 总复杂度：O(1) + O(n) + O(n²) = O(n²)
这里有个原则：取最高阶。O(n²) 是主导项，O(n) 和 O(1) 在 n 很大时可以忽略。
1.5 空间复杂度——内存也是成本
时间复杂度看时间，空间复杂度看内存。
说白了就是：你的算法额外占了多少存储空间。
常见的空间复杂度：
- O(1)：只用了几个变量，不随 n 变化
- O(n)：用了一个数组或哈希表，大小和 n 成正比
- O(n²)：用了二维矩阵
一个实用的经验：很多时候，时间复杂度和空间复杂度是「跷跷板」。你想跑得快，往往要多占内存；你想省内存，可能就要多花时间。比如缓存就是典型的「用空间换时间」。
1.6 最好、最坏、平均情况
同一个算法，面对不同的输入，表现可能天差地别。
拿快速排序来说：
- 最好情况：每次选的基准值正好在中间，O(n log n)
- 最坏情况：每次选的基准值都是最大或最小，退化成 O(n²)
- 平均情况：随机输入下，期望复杂度 O(n log n)
我个人习惯：关注最坏情况。因为线上环境，你永远不知道用户会给你什么数据。
避坑指南：我曾经写过一个哈希表的实现，以为平均 O(1) 就万事大吉。结果用户传了大量哈希冲突的数据，性能直接崩了。后来才意识到——哈希函数的设计、扩容策略，这些细节才是决定「平均情况」能不能成立的关键。
1.7 知识体系总览
下面这张图，帮你把本章的核心脉络串起来：
1.8 总结一下
复杂度分析，说白了就是三个问题：
- 数据规模 n 变大时，时间怎么涨？——时间复杂度
- 数据规模 n 变大时，内存怎么涨？——空间复杂度
- 最差情况下，会不会崩？——关注最坏情况
嗯，这一章的内容就到这。记住一句话：不懂复杂度，你写的代码就是盲盒。