瑞鑫是小狗

🚀 由数据范围反推算法复杂度

💡 算法竞赛必备：通过数据范围，快速判断可能使用的算法。

在算法竞赛中，数据范围往往是寻找解题思路的重要突破口。

通常可以根据题目给定的 n，结合时间限制，估算程序允许的时间复杂度，从而缩小算法选择范围。

📊 时间复杂度速查表

⚠️ 注意： 以上是常见时间限制下的经验参考，并非严格标准。实际还需要考虑时间限制、常数大小、数据结构和具体实现。

🔴 一、指数级算法

📌 n ≤ 20 ~ 30

参考复杂度： O(2^n)、O(n × 2^n) 等

常见算法：

• DFS 搜索与剪枝
• 回溯算法
• 状态压缩 DP
• 折半搜索（Meet in the Middle）
• 排列枚举与组合枚举

💡 2^20 ≈ 10⁶，2^26.6 ≈ 10^8而 2^30 ≈ 10⁹。

因此，n = 30 时通常不能直接运行 O(2^n) 的算法，需要利用剪枝、折半搜索等方式优化。

🟠 二、立方级算法

📌 n ≤ 100

参考复杂度： O(n³)

常见算法：

• Floyd 最短路算法
• 区间动态规划（区间 DP）
• 三重循环动态规划
• 高斯消元算法
• 三维状态动态规划

💡 100³ = 10⁶，通常可以轻松通过。

🟡 三、平方级算法

📌 n ≤ 1,000

参考复杂度： O(n²) ~ O(n² log n)

常见算法：

• 二维动态规划
• 朴素 Dijkstra 最短路算法
• 朴素 Prim 最小生成树算法
• 二重循环枚举
• 部分图论算法
• Bellman-Ford 算法（复杂度为 O(VE)）

💡 1000² = 10⁶，平方级算法通常没有问题。

注意：图论算法的复杂度往往同时取决于点数 V 和边数 E。

🟢 四、根号级优化算法

📌 n ≤ 10,000

参考复杂度： O(n√n)

常见算法：

• 分块算法
• 块状链表
• 莫队算法
• 根号分治
• 根号分类讨论

💡 10⁴ × √10⁴ = 10⁶。

分块和莫队的具体复杂度还与操作次数、询问数量等因素有关。

🔵 五、对数线性级算法

📌 n ≤ 100,000

参考复杂度： O(n log n)

常见算法：

基础算法

• 排序算法（如 std::sort）
• 二分查找与二分答案
• 堆与优先队列
• set / map

数据结构

• 树状数组
• 线段树
• 稀疏表（ST 表）
• 平衡树

图论算法

• 拓扑排序
• 堆优化 Dijkstra
• 堆优化 Prim
• Kruskal 最小生成树

进阶算法

• 凸包算法
• 半平面交
• CDQ 分治
• 整体二分
• 后缀数组
• 树链剖分
• 动态树（Link-Cut Tree）

💡 10⁵ × log₂(10⁵) ≈ 1.7 × 10⁶。

注意：并非所有列出的算法整体复杂度都是 O(n log n)。

例如拓扑排序为 O(V + E)，堆优化 Dijkstra 通常为 O((V + E) log V)。

SPFA 的最坏时间复杂度为 O(VE)，不属于有保证的 O(n log n) 算法。

🟣 六、线性级算法

📌 n ≤ 1,000,000

参考复杂度： O(n)，或常数较小的 O(n log n)

常见算法：

线性算法

• 双指针
• 滑动窗口
• 单调栈
• 单调队列
• 前缀和与差分
• 哈希算法
• BFS / DFS 遍历
• 并查集
• KMP 字符串匹配
• AC 自动机

常数较小的对数线性算法

• std::sort
• 树状数组
• 堆与优先队列
• 堆优化 Dijkstra（视图的规模而定）

💡 n = 10⁶ 时，线性算法通常比较稳妥。

O(n log n) 是否能够通过，需要考虑操作常数和时间限制。

🟤 七、超大规模线性算法

📌 n ≤ 10,000,000

参考复杂度： O(n)

常见算法：

• 双指针扫描
• 滑动窗口
• 前缀和与差分
• KMP 字符串匹配
• AC 自动机
• 线性筛素数
• 线性遍历与计数

💡 当 n 达到千万级别时，应优先考虑线性或更低复杂度的算法。

同时需要特别注意内存占用，例如一个长度为 10⁷ 的 int 数组约占用 40 MB。

⚫ 八、根号级数论算法

📌 n ≤ 10⁹

参考复杂度： O(√n)

常见算法：

• 试除法判断质数
• 枚举整数因子
• 试除法质因数分解
• 部分数论枚举算法

💡 √10⁹ ≈ 31623。

对单个整数进行 O(√n) 的处理，通常非常高效。

🔥 九、对数级数论算法

📌 n ≤ 10¹⁸

参考复杂度： O(log n)

常见算法：

• 欧几里得算法（GCD）
• 快速幂
• 二进制位运算
• 二进制拆分
• 矩阵快速幂（固定维度）
• 数位 DP（复杂度还取决于状态数）

💡 log₂(10¹⁸) ≈ 60。

即使整数达到 10¹⁸，对数级算法通常也只需要几十轮迭代。

💎 十、高精度算法

📌 n ≤ 10¹⁰⁰⁰

当整数超出 long long 的表示范围时，需要使用高精度算法。

设整数的十进制位数为 k。

常见算法：

• 高精度加法：O(k)
• 高精度减法：O(k)
• 朴素高精度乘法：O(k²)
• 朴素高精度除法：复杂度取决于除数和实现
• 数位 DP：与位数和状态数有关

💡 此时不再根据整数本身的大小分析复杂度，而是根据整数的位数分析。

🌌 十一、超大整数与快速多项式运算

📌 n ≤ 10^(10⁶)

当一个整数拥有上百万位时，普通的高精度运算可能已经无法满足时间要求。

设整数的位数为 k。

常见算法：

• 高精度加法与减法：O(k)
• 快速高精度乘法
• FFT（快速傅里叶变换）
• NTT（数论变换）
• 快速多项式卷积

典型复杂度：

• 朴素乘法：O(k²)
• 基于 FFT / NTT 的快速卷积：O(k log k)

💡 FFT / NTT 主要用于加速乘法和卷积运算，并不是普通高精度加减法所必需的算法。

📝 算法复杂度对照

以下按常见渐近增长速度从小到大排列：

🎯 解题时如何判断时间复杂度？

拿到一道算法题，可以按照以下顺序思考：

1. 观察数据范围：确定 n、m、Q 等变量的最大值。
2. 观察时间限制：判断大致允许多少次操作。
3. 估算复杂度：筛选可能通过的算法。
4. 分析题目性质：判断能否使用贪心、DP、搜索、图论或数据结构。
5. 检查特殊情况：注意常数、空间复杂度以及极端数据。

⭐ 核心原则

数据范围决定复杂度上限，题目性质决定算法选择。

复杂度是寻找算法的线索，而不是判断算法是否正确的依据。

Keep Thinking · Keep Coding · Keep Improving 🚀

• 前往 “题库” 面板，查看创建的示例题目是否正常工作。
• 使用超级管理员账号登录，通读 控制面板 -> 系统设置 页面，按需配置。

如果您需要可以直接导入的题目，可以 加入 Hydro 用户群 或是 从 Hydro 题库下载 。
您也可以下载 一本通编程启蒙 和 深入浅出程序设计竞赛（基础篇） 题库并按照压缩包内说明导入系统。
如果您需要题目配置指南，可以 查看文档 或是 查看配置示例 。

当你已经熟悉本系统的操作，可以在 管理域 > 编辑域资料 页面修改这条置顶信息。