算法复杂度分析：大O表示法、时间复杂度、空间复杂度、常见算法复杂度对比
聊到性能优化，绕不开的一个话题就是算法复杂度。我见过不少开发者，代码写得挺溜，一上线就卡成PPT。为什么？说白了，就是没算清楚这段代码到底要吃多少资源。
今天咱们就把这块硬骨头啃下来。你想想看，如果你能一眼看出一个算法是O(n²)还是O(log n)，那优化方向就清晰多了。
大O表示法：到底在描述什么？
大O表示法，我习惯叫它「最坏情况下的增长趋势」。它不关心你的机器是i3还是i9，也不管数据量是100还是1000。它只回答一个问题：当输入规模n变得非常大时，运行时间会怎么涨？
举个例子。你写个循环遍历数组，n=10时跑1毫秒，n=1000时跑100毫秒。嗯，这就是线性增长，记作O(n)。
核心要点：大O描述的是上界，是算法在最糟糕情况下的表现。不是平均，不是最好，是最坏。
我在项目中遇到过一位同事，他写了个排序函数，测试时数据量小，跑得飞快。结果上线后用户数据一多，直接超时。一查，他用了冒泡排序，O(n²)的复杂度。这就是没算大O的后果。
时间复杂度：代码跑多快？
时间复杂度衡量的是基本操作执行的次数。注意，不是秒数，是次数。因为秒数跟硬件有关，次数才是算法本身的属性。
咱们看几个常见的时间复杂度：
| 复杂度 | 名称 | 典型场景 |
|---|---|---|
| O(1) | 常数时间 | 数组按索引访问 |
| O(log n) | 对数时间 | 二分查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序（平均） |
| O(n²) | 平方时间 | 冒泡排序、嵌套循环 |
| O(2ⁿ) | 指数时间 | 递归斐波那契（未优化） |
为什么会这样？因为不同的操作次数增长曲线完全不同。n=1000时，O(n)执行1000次，O(n²)执行100万次。差距就是这么来的。
# O(1) 示例：直接访问
def get_first(arr):
return arr[0] # 不管数组多大，就一步
# O(n) 示例：线性查找
def find(arr, target):
for item in arr: # n越大，循环次数越多
if item == target:
return True
return False
# O(n²) 示例：冒泡排序
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
我的小技巧：分析时间复杂度时，先找循环。一层循环通常是O(n)，两层嵌套就是O(n²)。递归的话，看递归树的深度和分支数。
空间复杂度：内存吃多少？
时间复杂度管的是时间，空间复杂度管的是内存。说白了，就是你的算法额外开辟了多少存储空间。
我曾经接手过一个数据处理服务，每天凌晨跑批任务，总是内存溢出。查了半天，发现是某个函数为了排序，把整个数据集复制了一份又一份。空间复杂度从O(1)直接飙到了O(n²)，不爆才怪。
常见的空间复杂度：
- O(1)：只用了几个变量，不随输入规模变化
- O(n)：需要额外存储一个跟输入规模线性相关的数组或哈希表
- O(n²)：需要二维矩阵或大量递归调用栈
# O(1) 空间：只用了常数个变量
def sum_arr(arr):
total = 0
for num in arr:
total += num
return total
# O(n) 空间：创建了一个新数组
def copy_arr(arr):
new_arr = []
for item in arr:
new_arr.append(item)
return new_arr
避坑指南：我曾经在递归函数里忘记考虑调用栈的空间。递归深度为n时，空间复杂度就是O(n)。如果n是10万，栈直接爆掉。所以能用迭代就别用递归，除非你能控制深度。
常见算法复杂度对比
咱们把常用的算法拉出来遛遛，看看它们的复杂度：
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 二分查找 | O(1) | O(log n) | O(log n) | O(1) |
| 哈希表查找 | O(1) | O(1) | O(n) | O(n) |
| 二叉树遍历 | O(n) | O(n) | O(n) | O(n) |
你注意看，快速排序的最坏情况是O(n²)。为什么？因为如果每次选的基准值都是最大或最小，那递归树就退化成链表了。我建议你在实现快排时，用随机选基准或者三数取中法来避免这种情况。
知识体系总览
下面这张图，是我梳理的算法复杂度分析的核心脉络。你一看就明白各个概念之间的关系了。
怎么在实际中应用？
光背概念没用，得会用。我给你三个实战建议：
- 写代码前先估算：动手之前，花30秒算算你的算法大概是什么复杂度。如果数据量是10万，O(n²)基本就别想了。
- 用空间换时间：我经常这么干。比如用哈希表把O(n)的查找变成O(1)，虽然多占点内存，但值了。
- 关注瓶颈：别优化那些只占1%时间的代码。用性能分析工具跑一遍，找到最耗时的函数，看它的复杂度能不能降一档。
一个小经验：面试时被问到复杂度，别只背答案。说说你实际项目中怎么权衡时间和空间的。比如我上次优化一个日志分析系统，就是把O(n²)的嵌套循环改成了O(n)的哈希表方案，处理时间从2小时降到了3分钟。
好了，算法复杂度这块就聊到这儿。记住一句话：复杂度分析不是纸上谈兵，它是你写每一行代码时心里那杆秤。下次写循环前，先问问自己——这个操作，数据量翻10倍时，还能扛得住吗？