STUDY LINKS · PERSONAL NAVIGATION
学习网站导航
把自己的学习网站收进一页可编辑的书架。主入口指向 OI Wiki，复杂度速查保留为默认条目；之后可以添加、修改、删除，也可以随时恢复默认。
自定义条目保存在当前浏览器 localStorage · studyResourcesMY STUDY SHELF
我的学习书架
像整理活页夹一样管理入口。外链会在新标签页打开，删除内置条目后可用“恢复默认”找回。
0 个站点
导航数据只写在本机 localStorage 的 studyResources 键中，不会上传服务器。
复杂度速查附页 Θ、O、Ω、o 与常见增长速度 展开附页
ASIDE PAGE · QUICK REFERENCE
渐进记号
设 f(n) 与 g(n) 是定义在正整数上的函数。渐进记号描述的是增长趋势，而不是某个具体输入下的运行时间。
Θ
渐进紧确界
存在正常数 c₁、c₂、n₀，使 c₁g(n) ≤ f(n) ≤ c₂g(n)。增长阶相同。
O
渐进上界
存在 c、n₀，使 0 ≤ f(n) ≤ c·g(n)。只保证“不会比它更快地增长”。
Ω
渐进下界
存在 c、n₀，使 0 ≤ c·g(n) ≤ f(n)。说明增长至少达到这个量级。
o
非紧确上界
f(n)/g(n) → 0。f 的增长严格慢于 g，例如 n = o(n²)。
ω
非紧确下界
f(n)/g(n) → ∞。f 的增长严格快于 g，例如 n² = ω(n)。
常被写在题解里的 O 往往被当作“大约的复杂度”。严格地说，O 只是上界；要表达上下界相同，应使用 Θ。
常见复杂度排序
从低到高 · 条形长度仅表示相对增长速度
| 记号 | 增长速度 | 典型场景 |
|---|---|---|
| O(1) | 哈希表均摊查找、数组按下标访问 | |
| O(log n) | 二分查找、平衡树查找、快速幂 | |
| O(n) | 遍历数组、单层循环、线性筛 | |
| O(n log n) | 归并排序、堆排序、按权值排序后的并查集 | |
| O(n²) | 双重循环、Floyd 最短路、邻接矩阵遍历 | |
| O(2ⁿ) | 枚举子集、未剪枝的搜索、简单递归斐波那契 | |
| O(n!) | 全排列枚举、旅行商问题的暴力搜索 |
增长速度
O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2ⁿ)<O(n!)
前往 OI Wiki 查看完整讲解
包含定义、运算规则、主定理与常见误区。外链会离开当前工作台，不在页面内嵌入 iframe。