WARNING

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

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

[橘调蜜桃色]

🎯 1. 核心概述

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

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

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

🧠 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. 内存与数据类型基础

示例：若算法复杂度为 $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 因素综合判断，最终决定是否需要采用分治、离线、数学变换等高级优化技巧。