复杂度分析与算法选型指南

目录

• 核心概念
• 时间复杂度速查表
• 空间复杂度要点
• 从数据范围反推算法
• 回溯 vs DP：如何选择
• 例题

---

核心概念

时间复杂度：算法执行时间随输入规模增长的趋势，用大 O 表示法。

为什么重要：选错算法 → 超时。先算复杂度，再写代码，是最高效的策略。

---

时间复杂度速查表

以下数据基于“1 秒内能跑完”的经验值（C++ 标准，JS 打 3~5 折）：

复杂度	n 上限	典型算法	示例问题
O(n!)	n ≤ 10	全排列回溯	N 皇后
O(2ⁿ)	n ≤ 25	子集枚举	背包 DFS
O(n³)	n ≤ 500	Floyd、矩阵乘法	全源最短路
O(n²)	n ≤ 10⁴	二维 DP	编辑距离、网格路径
O(n·√n)	n ≤ 10⁵	分块	区间查询
O(n log n)	n ≤ 10⁶	排序、贪心	合并区间
O(n)	n ≤ 10⁷	线性扫描	最大子数组
O(log n)	n 任意	二分查找	搜索插入位置

常见操作的复杂度

操作	复杂度	说明
单层循环	O(n)	for (let i = 0; i < n; i++)
双层循环	O(n²)	嵌套 for
三层循环	O(n³)	Floyd 算法
递归（分治）	O(n log n)	归并排序
递归（每次减半）	O(log n)	二分查找
递归（每次减 1）	O(n)	线性递归
DFS/BFS 遍历图	O(V + E)	拓扑排序
组合数 C(n, k)	O(2ⁿ) 级别	子集枚举

---

空间复杂度要点

复杂度	典型场景
O(1)	原地操作，几个变量
O(n)	一维 DP 数组
O(n²)	二维 DP 矩阵
O(V + E)	图的邻接表

JS 中注意：递归深度也是空间消耗，V8 默认栈约 1 万层。

---

从数据范围反推算法

拿到题目先看 n 的范围，倒推该用什么算法：

n ≤ 10~15     → O(n!) 或 O(2ⁿ)    → 回溯、全排列
n ≤ 25~30     → O(2ⁿ)              → 状态压缩 DP、子集枚举
n ≤ 100       → O(n³)              → Floyd、区间 DP
n ≤ 10³       → O(n²)              → 二维 DP、简单图遍历
n ≤ 10⁴       → O(n²) 勉强 / O(n log n) → DP、排序
n ≤ 10⁵       → O(n log n)         → 排序、贪心、堆
n ≤ 10⁶~10⁷  → O(n)               → 线性扫描、前缀和
n ≤ 10⁹      → O(log n) 或 O(1)   → 二分、数学公式

口诀：n 多大决定了你能写几层循环。

---

回溯 vs DP：如何选择

这是最容易踩坑的地方。核心判断标准：

回溯适用场景

• 求所有方案（所有路径、所有组合、所有排列）
• n 很小（通常 ≤ 20~30）
• 需要输出具体方案内容

DP 适用场景

• 求最优值（最少、最多、最小、最大）
• 求方案数（不需要列出具体方案）
• 有重叠子问题（同一个状态被反复计算）
• n 较大（≥ 50）

判断流程

问题要求什么？
  ├─ 列出所有方案 → 回溯（前提 n 很小）
  ├─ 求最少/最多/最优值
  │   ├─ n ≤ 20 → 回溯也可以（但 DP 更优）
  │   └─ n ≥ 50 → 必须 DP
  └─ 求方案数
      ├─ 不需要列出 → DP
      └─ 需要列出 → 回溯（n 必须小）

从回溯到 DP 的思维转换

回溯是“一条路走到黑”，DP 是“逐层推进，复用结果”。

回溯视角（纵向）：
  start → 选择1 → 选择2 → ... → end  （每条路径独立计算）

DP 视角（横向）：
  第1层全算完 → 第2层全算完 → ... → 最后一层  （每层只算一次）

自问法：到当前状态时，“怎么来的”还重要吗？

• 重要 → 回溯（需要记录路径）
• 不重要（只关心最优值）→ DP

---

例题

例题 1：网格路径最少转向（DFS vs DP）

题目：m×n 网格，只能向右或向下走，0 可通行、非 0 障碍。求从 (0,0) 到 (m-1,n-1) 的最少转向次数。m,n ≤ 100。

DFS 回溯复杂度：路径数 C(m+n-2, m-1)，m=n=100 时约 10⁵⁸ → 超时

DP 复杂度：O(m×n) = 10⁴ → 轻松通过

教训：看到“最少” + “网格” + n ≥ 50，直接 DP，别想回溯。

---

例题 2：子集和问题

题目：给定数组 nums 和目标 target，判断是否存在子集和为 target。n ≤ 20 vs n ≤ 100。

分析：

• n ≤ 20：回溯 O(2²⁰) ≈ 10⁶ → 可行
• n ≤ 100：回溯 O(2¹⁰⁰) ≈ 10³⁰ → 不可行，必须用 DP（背包）O(n×target)

---

例题 3：全排列 vs 排列数

题目：给定 n 个不同元素。

求所有排列：必须回溯 O(n!)，n 只能 ≤ 10 求排列数：数学公式 O(1)，n 任意大

同样的问题，要求不同，算法天差地别。

---

例题 4：判断有向图是否有环

题目：n 个节点，m 条边，判断是否有环。n ≤ 100 vs n ≤ 10⁵。

分析：

• n ≤ 100：Floyd O(n³) = 10⁶ → 可以（跑完看 dist[i][i] 是否被更新，即是否存在 i→…→i 的路径），但不是最优
• n ≤ 10⁵：必须拓扑排序/DFS 三色标记 O(V+E)

Floyd 判环代码示例（n ≤ 100 可用）：

function hasCycleFloyd(n, edges) {
    // 初始化距离矩阵
    const dist = Array.from({ length: n }, (_, i) =>
        Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity))
    );
    // 建图
    for (const [u, v] of edges) {
        dist[u][v] = 1; // 无权图，有边就设为 1
    }
    // Floyd 三重循环
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    // 检查对角：dist[i][i] 被更新（不再是 0）→ i 能回到 i → 有环
    for (let i = 0; i < n; i++) {
        if (dist[i][i] !== 0) return true;
    }
    return false;
}

拓扑排序判环代码示例（n ≤ 10⁵ 推荐）：

function hasCycleTopo(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    let count = 0;
    while (queue.length) {
        const cur = queue.shift();
        count++;
        for (const next of graph[cur]) {
            if (--indegree[next] === 0) queue.push(next);
        }
    }
    return count < n; // 有剩余节点 → 有环
}

教训：即使算法正确，也要选复杂度匹配的。n=100 两种都能过，n=10⁵ 只有拓扑排序能过。

---

复杂度自查清单

每次做题前问自己：

1. n 最大是多少？
2. 我的算法几层循环？嵌套复杂度是多少？
3. 操作次数在 10⁷ 以内吗？
4. 有没有重叠子问题可以 DP 优化？
5. 递归深度会不会爆栈？

---

总结

口诀	含义
先看 n，再选法	数据范围决定算法
求所有用回溯，求最优用 DP	输出要求决定框架
n 小回溯爽，n 大 DP 稳	20 是分水岭
一题多解练手感	回溯 + DP 对比练习