3. 算法复杂度基础：大O表示法、时间/空间复杂度分析、常见复杂度对比
聊性能优化，绕不开复杂度分析。很多人觉得这是理论课，其实不然。我这些年做差分算法选型，踩过的坑十有八九都能追溯到复杂度估算失误。说白了，不懂复杂度，你连两个算法谁快都说不清楚。
3.1 大O表示法：别被名字吓到
大O表示法，核心就一句话：描述算法执行时间随数据规模增长的趋势。它不关心具体秒数，只关心“当数据量翻倍时，时间怎么变”。
举个例子。你写个循环找数组最大值：
int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}数组长度 n 翻倍，循环次数也翻倍。这就是 O(n)——线性时间。大O表示法忽略常数项和低阶项，只保留最高阶。所以 3n+100 次操作，大O依然是 O(n)。
3.2 时间复杂度分析：从代码到数学
分析时间复杂度，我一般分三步走：
- 找基本操作——通常是循环体、递归调用、比较操作
- 算执行次数——用输入规模 n 表示
- 取最高阶——去掉常数和低阶项
来看个经典例子——二分查找：
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}每次循环，搜索范围减半。n 个元素，最多需要 log₂n 次比较。所以时间复杂度是 O(log n)。
我曾经接手过一个日志分析系统，每天处理上亿条记录。原团队用线性查找匹配关键字，每次查询要扫描全量数据。改成哈希索引后，O(1) 的查找时间让系统响应从秒级降到毫秒级。嗯，这就是复杂度优化的威力。
3.3 空间复杂度：别只盯着时间
空间复杂度分析套路和时间复杂度一样，只不过统计的是额外内存消耗。我见过不少开发者只优化时间，结果内存爆了。
举个例子，递归实现的斐波那契数列：
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}时间复杂度 O(2ⁿ)，空间复杂度 O(n)——因为递归调用栈深度最多 n 层。但如果你用数组缓存中间结果：
int fib(int n) {
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}时间复杂度降到 O(n)，空间复杂度也是 O(n)。用空间换时间，这是最常见的权衡策略。
3.4 常见复杂度对比：一张表说清楚
下面这张表，我建议你记在脑子里。选型时对照着看，基本不会跑偏。
| 大O | 名称 | n=100时操作数 | 典型算法 | 评价 |
|---|---|---|---|---|
| O(1) | 常数时间 | 1 | 哈希表查找、数组随机访问 | 理想，但往往有代价 |
| O(log n) | 对数时间 | 7 | 二分查找、平衡树操作 | 非常快，适合大数据 |
| O(n) | 线性时间 | 100 | 线性扫描、简单遍历 | 可接受，数据量大时需优化 |
| O(n log n) | 线性对数 | 700 | 归并排序、快速排序 | 优秀排序算法的天花板 |
| O(n²) | 平方时间 | 10,000 | 冒泡排序、嵌套循环 | n>1000时基本不可用 |
| O(2ⁿ) | 指数时间 | 1.27e30 | 暴力递归、子集枚举 | n>20就爆炸 |
你想想看，O(n²) 在 n=1000 时就是百万级操作，而 O(n log n) 才一万左右。差了两个数量级。选算法时，优先看能不能把复杂度降一阶。
3.5 复杂度分析实战：差分算法选型
回到我们的课程主题。做差分算法选型时，复杂度分析是第一步。我一般这样评估：
- 数据规模：待比较的数据集有多大？百万级还是十亿级？
- 操作频率：差分计算是一次性还是持续进行？
- 资源限制：内存够不够？CPU 有没有余量？
举个例子。如果你要比较两个 10 万行的配置文件，用 O(n²) 的逐行对比，那就是 100 亿次操作。换成 Myers 差分算法（O(nd) 复杂度，d 是差异行数），通常几万次操作就能搞定。这就是为什么 Git 用 Myers 而不是暴力法。
3.6 知识体系图
下面这张图，把复杂度分析的核心脉络画出来了。建议你保存下来，选型时对照着看。
复杂度分析不是纸上谈兵。它是你选算法、做优化时的第一把尺子。我每次做技术方案评审，第一件事就是让团队把核心算法的复杂度写出来。写不清楚的，方案大概率有问题。