1. 概述
本文将深入讲解 Big O 符号的实际含义，并通过多个 Java 示例，直观展示不同时间复杂度对代码执行效率的影响。掌握这些知识，能帮你写出更高效的算法，避免在性能上“踩坑”。
2. Big O 符号的直观理解
我们经常听到某个算法的性能用 Big O 符号 来描述。算法性能分析（也叫算法复杂度分析）属于 算法分析 领域，主要关注算法执行时消耗的资源，比如时间或内存。
本文重点关注 时间资源。通常来说，算法执行时间越短，性能越好。Big O 关注的是：当输入规模增长时，运行时间如何变化。✅ 理解增长趋势，比纠结具体耗时更重要。
3. 常数时间算法 – O(1)
输入规模如何影响运行时间？关键在于理解不同增长速率。这里我们关注的是：每单位输入所消耗的时间。
看下面这段代码：
int n = 1000;
System.out.println("Hey - your input is: " + n);
无论 n 是多少，这段代码的执行时间都是固定的，与输入大小无关。
再看这个例子：
int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);
虽然执行了 3 次打印，耗时可能是上一个例子的 3 倍，但依然 与 n 的大小无关。这类算法称为 常数时间算法，记作 *O(1)*。
⚠️ 注意：O(2)、O(3) 甚至 O(1000) 都等价于 *O(1)*。Big O 不关心常数因子，只关心是否随输入增长。
4. 对数时间算法 – O(log n)
常数时间最快，接下来就是 对数时间。这类算法理解起来稍微抽象一点。
最常见的例子是 **二分查找**。其核心思想是每次将搜索范围减半，因此运行时间与输入的对数（以 2 为底）成正比。
for (int i = 1; i < n; i = i * 2){
System.out.println("Hey - I'm busy looking at: " + i);
}
如果 n 是 8，输出为：
Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4
循环执行了 log₂(8) = 3 次。✅ 增长极其缓慢，性能非常优秀。
5. 线性时间算法 – O(n)
比对数时间慢的是 线性时间算法。所谓线性增长，就是运行时间与输入规模 n 成正比。
最典型的例子是单层循环：
for (int i = 0; i < n; i++) {
System.out.println("Hey - I'm busy looking at: " + i);
}
循环执行 n 次。我们不关心每次迭代具体耗时，只关心它随 n 线性增长。
即使改成这样：
for (int i = 0; i < n; i++) {
System.out.println("Hey - I'm busy looking at: " + i);
System.out.println("Hmm.. Let's have another look at: " + i);
System.out.println("And another: " + i);
}
虽然每次迭代做了 3 次操作，但总执行次数仍是 3n，依然属于 线性增长。我们记作 *O(n)*。
✅ 核心：O(2n+1) 和 O(n) 被视为等价。Big O 只关注最高次项和增长趋势，忽略常数项和低阶项。
6. 线性对数时间算法 – O(n log n)
这是下一个复杂度层级。运行时间与 n log n 成正比。
典型例子是嵌套循环，其中内层循环是对数时间：
for (int i = 1; i <= n; i++){
for(int j = 1; j < n; j = j * 2) {
System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
}
}
外层循环 n 次，内层循环 log n 次，总执行次数约为 n * log n。
例如，当 n=8 时，执行次数为 8 * log₂(8) = 8 * 3 = 24 次。
⚠️ 在分析 Big O 时，循环条件中的 <= 还是 < 通常不影响最终结论。
7. 多项式时间算法 – O(n^p)
这类算法比 O(n log n) 更慢。"多项式" 是一个统称，包含二次方 *(n²)*、三次方 *(n³)*、四次方 (n⁴) 等。
关键点：
- ✅ O(n²) 比 O(n³) 快
- ✅ O(n³) 比 O(n⁴) 快
- 复杂度随指数增加而急剧恶化
看一个简单的 O(n²) 算法：
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
}
}
当 n=8 时，执行 8² = 64 次。
⚠️ 如果再嵌套一层循环，复杂度就变成 O(n³)，性能会显著下降。
8. 指数时间算法 – O(k^n)
⚠️ 警告：进入危险区域！这类算法的运行时间随输入规模呈指数级增长。
例如：
- **O(2^n)**：每增加一个输入，运行时间翻倍
- **O(3^n)**：每增加一个输入，运行时间变为 3 倍
- **O(k^n)**：每增加一个输入，运行时间变为 k 倍
简单示例：
for (int i = 1; i <= Math.pow(2, n); i++){
System.out.println("Hey - I'm busy looking at: " + i);
}
当 n=8 时，循环执行 2^8 = 256 次。随着 n 增大，执行次数爆炸式增长，实际项目中应极力避免。
9. 阶乘时间算法 – O(n!)
在大多数情况下，这已经是性能最差的级别了。运行时间与输入规模的阶乘成正比。
经典案例是使用 暴力穷举法 解决 **旅行商问题**。其时间复杂度为 O(n!)，因为需要检查所有可能的城市排列。
简单示例：
for (int i = 1; i <= factorial(n); i++){
System.out.println("Hey - I'm busy looking at: " + i);
}
其中 factorial(n) 计算 n!。当 n=8 时，算法执行 8! = 40320 次。✅ 可以看出，这类算法仅适用于极小的输入。
10. 渐近函数
Big O 是一种渐近函数。它只关心算法在输入规模趋于无穷大时的性能表现。
关键点：
- ✅ Big O 关注的是极限情况下的性能（例如排序一亿个数 vs. 排序 5 个数）
- ❌ 它不关心小规模输入下的具体表现
- ✅ 除了 Big O，还有 Big Θ (Theta) 和 Big Ω (Omega)，它们都描述算法在极限下的行为
三者区别（用集合论理解）：
- Big O：上界，描述算法最坏情况下的运行时间（“不会比这个更差”）
- Big Ω：下界，描述算法最好情况下的运行时间（“不会比这个更好”）
- Big Θ：紧确界，描述算法运行时间的精确阶数（“就等于这个”）
虽然日常交流中我们常用 Big O 泛指复杂度，但了解三者的区别会让你的分析更严谨。
11. 总结
本文通过 Java 示例讲解了 Big O 符号的核心概念，展示了不同时间复杂度对算法性能的巨大影响。
- ✅ 掌握复杂度分析，能帮你快速识别代码中的性能瓶颈
- ✅ 优先选择 O(1)、O(log n)、O(n) 和 O(n log n) 的算法
- ❌ 尽量避免 O(n²) 以上的算法，尤其是 O(2^n) 和 O(n!)，它们在大数据量下会“原地爆炸”
一个直观展示各种复杂度对比的图表可以参考：Big O Cheat Sheet。
文中所有代码示例均可在 GitHub 上找到：https://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-3