学数据结构和算法，绕不开两个数学概念：对数与指数。名字听着唬人，核心其实一句话能说清——对数问的是"我能除几次"，指数问的是"我能乘几次"。把这句话想明白，O(log n)和O(2ⁿ)就不再是天书。
指数：每加一步，结果翻倍
先看一组数：2¹=2，2²=4，2³=8，2⁴=16，2⁵=32，2⁶=64，2⁷=128。规律很直白，n每增加1，结果就翻一倍，这就是指数增长，通用形式写作2ⁿ。
把n拉大一点，感受会更强烈：
- 2¹⁰ = 1,024
- 2²⁰ = 1,048,576
- 2³⁰ = 1,073,741,824
涨得非常快。这在算法里为什么重要？因为有些问题在每一步都给你多个选择。比如"取它"或者"不取它"：一个元素对应2种选择，两个元素对应4种，三个元素对应8种。n个元素，就是2ⁿ。
这就是子集问题、穷举所有选择、以及部分回溯类问题复杂度会写成O(2ⁿ)的原因——每往下走一层，可能性就翻一倍。
对数：反过来问，要除几次
对数问的是相反的问题。已知2³=8，那么"2的多少次方等于8"？答案是3，写成log₂(8)=3。所以2³=8和log₂(8)=3是一体两面，对数和指数互为逆运算。
理解log n最省事的办法，是盯着"反复除以2"这个过程看。从1,000,000开始：1,000,000 → 500,000 → 250,000 → 125,000 → 62,500 → …… → 1。从一百万降到1，只需要大约20次除法，因为log₂(1,000,000)≈20。
这正是对数增长在算法里好用的地方：哪怕n变得极大，步数增长也慢得惊人。
二分查找就是活教材
假设有1,000,000个已排序的数字，要找出其中一个。普通查找可能从1开始一个个试：1、2、3、4、5……最坏情况是O(n)。
二分查找换了打法：先看中间那个，一次砍掉一半剩余数据。1,000,000 → 500,000 → 250,000 → 125,000 → …… → 1。因为搜索空间不断被除以2，二分查找的复杂度就是O(log n)。
把两者摆在一起，差距一目了然：
- n=10：log₂(n)约3，2ⁿ=1,024
- n=20：log₂(n)约4，2ⁿ=1,048,576
- n=30：log₂(n)约5，2ⁿ=1,073,741,824
- n=40：log₂(n)约5，2ⁿ=1,099,511,627,776
log n慢得几乎不动，2ⁿ快得离谱。所以规律可以这样记：O(log n)常见于我们不断缩小问题的场景，O(2ⁿ)常见于我们不断制造新可能性的场景。
代码里直接看
对数形态的循环长这样：
let n = 1000000;
while (n > 1) {
n = Math.floor(n / 2);
}
每次迭代把问题砍一半，时间复杂度O(log n)。
指数形态的递归长这样：
function solve(n) {
if (n === 0) return;
solve(n - 1);
solve(n - 1);
}
每次函数调用又生出两个新调用，调用数量不断翻倍，复杂度大约是O(2ⁿ)。
不用背定义，认模式就行
回到算法本身，其实不需要记住复杂的数学定义，只要认出模式：看到"问题被反复对半切"，就往对数上想，对应O(log n)；看到"每个元素都分叉出多个选择"，就往指数上想，对应O(2ⁿ)。
一个在缩，一个在炸。分清这两件事，很多复杂度分析题就不用硬算了。
热门跟贴