第七讲 · 时间复杂度分析 原创

⏱️ 算法时间复杂度速查手册

一页掌握核心，助你根据输入规模，秒选算法思路！

[橘调蜜桃色]

---

🎯 1. 核心概述

在算法竞赛（ACM）或技术笔试中，时间限制通常为 1秒 或 2秒。在这样的限制下，C++ 代码的单秒计算量级普遍估计在 ${10}^7\sim {10}^8$ 次基本操作。因此，在动手编码前，预估算法复杂度与数据规模的匹配度是至关重要的一步。

下面，我们将常见的数据规模与对应的最优时间复杂度进行映射，并给出算法实现建议。

📊 2. 数据规模 vs. 推荐算法复杂度

数据规模 (n)	推荐时间复杂度	常用算法 / 数据结构	💡 备注
n ≤ 30	$O(2^n)$ 或更高	DFS + 剪枝、状态压缩 DP、子集枚举	适用于暴力穷举或状态压缩
n ≤ 100	$O(n^3)$	Floyd-Warshall、三重循环 DP、高斯消元	小规模图论、矩阵或动态规划
n ≤ 1,000	$O(n^2)$	朴素 DP、Dijkstra/Prim、Bellman-Ford	二维网格、邻接矩阵等场景
n ≤ 10,000	$O(n\sqrt{n})$	分块算法、莫队算法	适用于需要平衡查询与修改的场景
n ≤ 100,000	$O(n\log n)$	排序、线段树、树状数组、堆、并查集、Dijkstra+堆、Kruskal、树链剖分	最主流的竞赛数据规模
n ≤ 1,000,000	$O(n)$ 或 $O(n\log n)$	单调队列/栈、双指针、哈希、KMP、AC自动机、线性筛	对算法常数和内存有一定要求
n ≤ 10,000,000	$O(n)$	双指针、线性扫描、线性筛素数	要求高效的线性算法
n ≤ 109	$O(\sqrt{n})$	质数判断（试除法）	通常与数论或数学优化相关
n ≤ 1018	$O(\log n)$	快速幂、二分查找、辗转相除法 (GCD)	适用于大数计算或值域搜索
超大数	$O((\log n{)}^k)$	高精度计算、快速傅里叶变换 (FFT/NTT)	位数决定复杂度

---

🧠 3. 常见算法复杂度速览

• 排序 (std::sort): $O(n\log n)$
• 二分搜索: $O(\log n)$ (数组查找) 或 $O(\log V)$ (值域二分)
• Dijkstra (堆优化): $O((E+V)\log V)$
• Kruskal (并查集): $O(E\log E)$
• 线段树 / 树状数组: 单次操作 $O(\log n)$
• KMP / AC 自动机: 构造与匹配均为 $O(n+m)$ 线性时间

---

🧭 4. 算法可行性快速自检清单

1. 确定复杂度：将你的算法思路表示为 $f(n)$ 的形式。
2. 代入规模：将题目给出的最大数据规模 n 代入 $f(n)$，估算总操作次数。
3. 检查上限：估算结果是否在 ${10}^7\sim {10}^8$ 的安全范围内？
4. 考虑常数：你的实现是基于常数较小的位运算、数组，还是常数较大的 std::map 或递归？
5. 评估 I/O：输入/输出量是否过大？如果超过 10^6，务必使用快速 I/O。

动态规划复杂度估算： 总计算量 = 状态总数 × 单个状态的转移计算量

---

💾 5. 内存与数据类型基础

名称	含义	字节 (Byte)
1 Byte	8 bit	1
1 KB	1024 Byte	1,024
1 MB	1024 KB	1,048,576
1 GB	1024 MB	1,073,741,824
int	32位整数	4
long long	64位整数	8
double	双精度浮点数	8
__int128	128位整数 (GCC/Clang)	16

示例：若算法复杂度为 $O(n\log n)$ 且 $n={10}^5$，则估算操作数约为 ${10}^5\times {\log }_2({10}^5)\approx {10}^5\times 16.6\approx 1.7\times {10}^6$ 次。这在 1秒 内通常是安全的。

---

💻 6. 高效 C++ 代码模板

🔢 快速幂 (迭代) — $O(\log k)$

long long power(long long base, long long k, long long mod) {
    long long res = 1;
    base %= mod;
    while (k > 0) {
        if (k & 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        k >>= 1;
    }
    return res;
}

🧮 欧几里得算法 (GCD) — $O(\log min(a,b))$

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

🧾 线性筛 (Euler 筛) — $O(n)$

vector<int> primes;
vector<int> min_prime(n + 1, 0);

void linear_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_prime[i] || (long long)p * i > n) break;
            min_prime[p * i] = p;
        }
    }
}

---

🛠️ 7. 实用技巧与优化

• 常数优化：位运算 (>>, &, ^) 远快于乘除；数组随机访问快于 std::map；unordered_map 通常比 map 快，但需警惕哈希冲突。

• 本地测试：如果不确定算法能否通过，先用最大规模数据在本地进行粗略的基准测试。

• 快速 I/O：当数据量巨大时，IO 可能成为瓶颈。请使用以下代码加速：

  // 在 main 函数开头加入
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

✅ 8. 总结

根据数据规模选择合适的复杂度是高效解题的第一步。利用此速查表，你可以快速定位算法类别，再结合常数、内存和 I/O 因素综合判断，最终决定是否需要采用分治、离线、数学变换等高级优化技巧。