面试问"这段代码时间复杂度多少"、看算法题解写 O(n log n)……大 O 是程序员绕不开的基础。这篇用最直白的话讲清它。
一、大 O 到底在描述什么
它描述的是：当数据量 n 变大时，程序运行时间增长得有多快。注意它只看"增长趋势"，忽略常数——所以 O(2n) 和 O(n) 都写作 O(n)。
二、常见的几种复杂度
- O(1) 常数：数组按下标取值、哈希表查找；数据再多也一步到位；
- O(log n) 对数：二分查找、平衡树操作；每步砍掉一半；
- O(n) 线性：遍历一遍数组、单层循环；
- O(n log n)：快速排序、归并排序；常见"最好也就这样"的排序；
- O(n²) 平方：双层嵌套循环、冒泡排序；数据一大就明显变慢；
- O(2ⁿ) 指数：暴力枚举子集；n 稍大就跑不动。
三、快速判断法
- 没有循环、只做固定几件事 → O(1)；
- 一层循环跑 n 次 → O(n)；
- 两层各自跑 n 次的嵌套循环 → O(n²)；
- 循环里每次范围减半（如
while(n) n/=2）→ O(log n)； - 多个循环并列相加，取最大的那个。
💡 实用原则：n 很大时，O(n log n) 和 O(n²) 的差距会大到离谱。同样是 10 万数据，前者秒出，后者可能跑几分钟。优化算法比换电脑有用得多。
四、和空间复杂度什么关系
空间复杂度看的是额外用了多少内存，写法一样（O(1)、O(n)…）。有时会用空间换时间，比如哈希表把查找从 O(n) 降到 O(1)。
五、常见问题
Q：为什么忽略常数？
因为数据量够大时，增长趋势才是决定性的。
Q：最好/最坏/平均要分开吗？
要。快速排序平均 O(n log n)，最坏会退化成 O(n²)。
广告位
此处为广告展示区，站点主粘贴发布商 ID 后自动展示。
此处为广告展示区，站点主粘贴发布商 ID 后自动展示。