算法复杂度分析 (Algorithm Complexity Analysis)
1. 核心概念概览
在计算机科学中，我们无法通过“运行这段代码花了多少秒”来准确评估一个算法的好坏，因为这受到硬件性能、当前系统负载等太多外界因素的影响。
因此，我们引入了渐进复杂度分析（Asymptotic Complexity Analysis），也就是我们常说的大 O 表示法（Big O Notation）。它主要关注当输入数据规模（n）趋于无穷大时，算法运行时间或内存占用的增长趋势。
1.1 大 O 表示法 (Big O Notation) 的核心法则
大 O 表示法用于描述算法在最坏情况下的时间或空间表现（有时也会分析平均情况）。在计算大 O 时，我们必须遵循以下三个核心法则：
- 只保留最高阶项： 随着
n变大，低阶项的影响微乎其微。例如，运行次数为 $2n^2 + 5n + 10$，我们只看 $2n^2$。 - 去掉常数系数： 常数系数在
n趋于无穷大时意义不大。上面的 $2n^2$ 最终会被记为 $O(n^2)$。 - 大 O 表示的是量级，而非精确次数。
2. 时间复杂度 (Time Complexity)
时间复杂度是指算法执行所需操作次数随数据规模 n 增长的趋势。
2.1 常见时间复杂度量级 (从优到劣)
| 符号 | 读法 / 名称 | 增长趋势 | 典型算法/操作代表 |
|---|---|---|---|
| $O(1)$ | 常数阶 (Constant) | 无论数据多少，时间不变 | 哈希表查找、数组索引访问 (arr[5])、简单数学计算。 |
| $O(\log n)$ | 对数阶 (Logarithmic) | 极其平缓，近乎完美 | 二分查找、二叉搜索树查找。通常出现于“每次砍掉一半”的场景。 |
| $O(n)$ | 线性阶 (Linear) | 数据翻倍，时间翻倍 | 数组遍历、顺序查找。 |
| $O(n \log n)$ | 线性对数阶 | 稍微陡于线性 | 快速排序、归并排序、堆排序的平均情况。通常出现于“分治 + 遍历”的场景。 |
| $O(n^2)$ | 平方阶 (Quadratic) | 数据增加，时间暴增 | 冒泡排序、选择排序、两层嵌套的 for 循环。 |
| $O(2^n)$ | 指数阶 (Exponential) | 数据稍大，直接死机 | 斐波那契数列的纯递归解法、部分回溯算法。 |
| $O(n!)$ | 阶乘阶 (Factorial) | 最差，毫无实用价值 | 全排列问题。 |
2.2 JavaScript 代码示例与时间复杂度分析
$O(1)$ - 常数阶
没有循环，没有与 n 相关的递归，即使代码有成百上千行，只要执行次数是固定的，就是 $O(1)$。
js
function getFirstElement(arr) {
const a = 1 + 1; // 1次操作
return arr[0]; // 1次操作
} // 总计 2 次，大O表示为 O(1)$O(n)$ - 线性阶
一层循环，循环次数直接受到输入规模 n 的影响。
js
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) { // 循环 n-1 次
if (arr[i] > max) max = arr[i];
}
return max;
} // O(n)$O(n^2)$ - 平方阶
双层嵌套循环，外层循环 n 次，内层也循环 n 次（或者 n 的某个比例，如 $n/2$）。
js
function printPairs(arr) {
for (let i = 0; i < arr.length; i++) { // 执行 n 次
for (let j = i; j < arr.length; j++) { // 平均执行 n/2 次
console.log(arr[i], arr[j]);
}
}
} // 总次数约为 n^2 / 2，忽略系数和低阶项，记为 O(n^2)$O(\log n)$ - 对数阶
循环条件每次都成倍地缩小范围。这是面试中最常要求优化的目标。
js
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
// 关键：每次排除一半的数据
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
} // O(log n)3. 空间复杂度 (Space Complexity)
空间复杂度是指算法在运行过程中临时占用存储空间大小的量度，同样使用大 O 表示法。
注意： 我们评估空间复杂度时，通常不包括输入数据本身所占的空间，只计算算法为了解决问题而额外开辟的内存空间（如临时数组、哈希表、递归调用栈等）。
3.1 常见空间复杂度分析
| 空间复杂度 | 典型场景 |
|---|---|
| $O(1)$ | 只使用了几个固定的辅助变量，不随输入规模 n 变化。（如冒泡排序、双指针遍历）。 |
| $O(n)$ | 创建了一个与输入规模长度相同的临时数组或哈希表；或者单分支的递归深度达到了 n。 |
| $O(n^2)$ | 创建了一个 n * n 的二维数组或矩阵（如某些图的邻接矩阵表示）。 |
| $O(\log n)$ | 快速排序或归并排序的递归调用栈深度。 |
3.2 递归的空间复杂度陷阱
很多初学者认为只要没有显式地 new Array()，空间复杂度就是 $O(1)$。这是大错特错的！
在递归算法中，系统必须为每一次函数调用分配“执行栈（Call Stack）”。递归的深度有多深，空间复杂度就有多大。
js
// 示例：求 1 到 n 的和（纯递归）
function sumRecursion(n) {
if (n === 1) return 1;
return n + sumRecursion(n - 1);
}
// 分析：为了计算 sumRecursion(n)，必须等 sumRecursion(n-1) 返回... 一路压栈。
// 栈的深度达到了 n 层。因此，虽然没有创建数组，但其 空间复杂度是 O(n)。
// （这也是为什么递归层数太多会引发 Stack Overflow 的原因）。4. 常见问题深度剖析 (FAQ)
| 常见疑惑 | 深度解析与应对策略 |
|---|---|
1. O(2n) 和 O(n) 有区别吗？ | 在大 O 表示法中没有区别，统一记为 $O(n)$。但在实际工程中，常数因子当然是有影响的。如果算法 A 是精确的 $n$ 次操作，算法 B 是精确的 $20n$ 次操作，两者复杂度都是 $O(n)$，但 A 肯定比 B 快很多。面试中可以说：“它的复杂度是 O(n)，但常数系数较小，实际性能更好。” |
| 2. 最好情况、最坏情况、平均情况，以哪个为准？ | 业界通常默认讨论的是最坏情况复杂度 (Worst-case Complexity)，因为它为算法的性能提供了“保底承诺”。 有些算法的最坏情况很难出现（如快速排序的最坏情况 $O(n^2)$，在加入随机化后极难发生），此时我们可能会重点讨论它的平均情况复杂度（快排的平均是 $O(n \log n)$）。 |
| 3. 时间和空间可以兼得吗？ | 很难。“空间换时间”是算法优化的最常用套路。例如：在一个无序数组中频繁查找某个值，每次遍历是 $O(n)$ 的时间，$O(1)$ 的空间。如果为了提速，我们建一个哈希表把数据存进去，查找时间降为 $O(1)$，但代价是空间复杂度飙升到了 $O(n)$。优秀的工程师就是要在业务场景中找到时间和空间的最佳平衡点。 |
| 4. 怎么判断我的算法够不够快？（估算技巧） | 在大部分算法竞赛或笔试系统中（如 LeetCode），服务器一秒钟大约能执行 $10^7$ 到 $10^8$ 次基础运算。 🔹 如果数据量 $n \approx 10^5$，你的算法必须是 $O(n \log n)$ 或 $O(n)$ 才能通过，写 $O(n^2)$ 绝对超时（Timeout）。 🔹 如果数据量 $n \le 100$，你可以放心地写 $O(n^3)$ 甚至回溯。 |