时间复杂度与空间复杂度：大O表示法、常见复杂度分析、空间换时间思想
聊到性能分析，绕不开的就是时间复杂度和空间复杂度。说白了，这就是衡量代码效率的两把尺子。我刚开始写代码那会儿，总觉得能跑就行，直到有一次线上服务因为一个O(n²)的循环把CPU打满了，用户反馈慢得像蜗牛……嗯，从那以后，我每次写核心逻辑都会先算算复杂度。
大O表示法：别纠结精确值，看趋势
大O表示法，其实不关心你的代码具体跑了多少毫秒。它关心的是：当数据量变大时，你的代码会变慢多少？
举个例子。你写个循环找数组里最大的数，数组有10个元素，循环10次；有100万个元素，循环100万次。时间跟数据量成正比——这就是O(n)。
我个人习惯把大O理解成「增长趋势」。O(1)是常数级，不管数据多大，时间基本不变。O(n)是线性级，数据翻倍，时间也翻倍。O(n²)就惨了，数据翻倍，时间变成4倍。
常见复杂度：从快到慢排个序
我整理了一张表，平时写代码时可以参考这个排序：
| 复杂度 | 名称 | 10个数据 | 1000个数据 | 典型场景 |
|---|---|---|---|---|
| O(1) | 常数阶 | 1 | 1 | 数组随机访问、哈希表查找 |
| O(log n) | 对数阶 | 约3 | 约10 | 二分查找、平衡二叉树 |
| O(n) | 线性阶 | 10 | 1000 | 单层循环、遍历数组 |
| O(n log n) | 线性对数阶 | 约33 | 约9966 | 归并排序、快速排序 |
| O(n²) | 平方阶 | 100 | 1,000,000 | 双层循环、冒泡排序 |
| O(2ⁿ) | 指数阶 | 1024 | 天文数字 | 递归斐波那契、穷举 |
你看，O(n²)在1000个数据时就已经是百万级别了。我在项目中遇到过有人用双层循环处理10万条数据，结果接口超时。后来改成哈希表，直接降到O(n)，问题秒解。
空间复杂度：内存不是免费的
时间复杂度讲的是时间，空间复杂度讲的就是内存。你想想看，如果为了快，把整个数据库都加载到内存里，那服务器扛得住吗？
空间复杂度的分析思路跟时间复杂度一样。O(1)表示只用了固定几个变量，O(n)表示用了跟数据量成正比的内存。
// 空间复杂度 O(1) —— 只用了几个变量
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}
// 空间复杂度 O(n) —— 创建了一个新数组
function double(arr) {
let result = [];
for (let i = 0; i < arr.length; i++) {
result.push(arr[i] * 2);
}
return result;
}空间换时间思想：最经典的优化策略
说白了，空间换时间就是「多花点内存，让程序跑得更快」。这是性能优化里最常用、最有效的手段之一。
举个例子。你有个函数要频繁判断某个数是不是质数。每次现算？那太慢了。不如提前算好存起来，查表就行。
// 空间换时间：预计算质数表
const primeCache = new Map();
function isPrime(n) {
if (primeCache.has(n)) return primeCache.get(n);
// 计算逻辑...
let result = true;
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) {
result = false;
break;
}
}
primeCache.set(n, result);
return result;
}这段代码，第一次调用时慢一点，后面再查同样的数，直接O(1)返回。这就是典型的空间换时间。
常见场景：什么时候该用空间换时间？
- 重复计算：同一个结果被反复计算，用缓存或备忘录
- 查找频繁：哈希表代替遍历，O(1)查找秒杀O(n)
- 排序辅助：用额外数组做计数排序，比比较排序快得多
- 动态规划：用数组存中间结果，避免重复递归
你想想看，如果一段代码每天被调用几百万次，哪怕每次省下1毫秒，一天就是几千秒。这点内存开销，值不值？
知识体系总览
下面这张图，把本章的核心逻辑串起来了。我建议你保存下来，写代码时对照着看。
嗯，这张图把时间复杂度和空间复杂度的关系讲清楚了。左边是时间，右边是空间，底部是核心思想。你写代码时，可以拿这张图当参考，看看自己写的代码落在哪个区间。
可可精品资料库