渐近记号

常数 $c$ 吸收机器、语言与实现的固定倍率差异，起点 $n_0$ 则忽略有限多个小输入上的反常。证明 $f\in O(g)$ 时，必须选出一组固定的 $c,n_0$，让它们同时覆盖此后的全部规模，不能在看见每个 $n$ 后重新选 $c$。反驳这个关系则要说明任意固定倍率最终都会被某些输入规模突破。

这使比较聚焦于输入放大时成本如何增长，得到 $\log n\prec n\prec n\log n\prec n^2\prec 2^n$ 这类结构性层次。$O(g)$ 只是上界函数类，紧确的同阶结论应写成 $\mathrm{\Theta }(g)$；小 $o$ 则更强，要求无论倍率取得多小，最终仍能作为上界。

$3n^2+5n+7\in \mathrm{\Theta }(n^2)$：当 $n\ge 1$ 时，$3n^2\le 3n^2+5n+7\le 15n^2$。对固定底数 $a,b>1$，换底公式说明 ${\log }_{a}n\in \mathrm{\Theta }({\log }_{b}n)$，所以对数复杂度通常不写底；指数的底则不能忽略，因为 $2^n\in o(3^n)$。函数也无须单调。例如 $f(n)=n^2+n\sin n$ 虽有振荡，当 $n\ge 2$ 时仍有

因而 $f\in \mathrm{\Theta }(n^2)$。又有 $n\log n\in o(n^{3/2})$，因为 $\log n/\sqrt{n}\to 0$。只写 $n\log n\in O(n^{3/2})$ 虽正确，却丢失了比值趋零这一更强信息。

$n\in O(n^2)$ 为真但不紧，因而上界不能单独证明最优性。“$f=O(g)$”是常见的历史写法，实质是成员关系 $f\in O(g)$，不可交换或移项；本库优先使用成员记法。定义也允许 $c$ 与 $n_0$ 大得惊人：常数因子为 ${10}^9$ 的 $\mathrm{\Theta }(n)$ 实现在一切现实规模上都可能输给常数温和的 $\mathrm{\Theta }(n\log n)$ 实现。渐近优势只是“最终”的承诺，现实输入仍受常数、内存层次和实现成本影响。

从执行次数到增长率 ​

若外层循环依次取 $i=1,\dots ,n$，第 $i$ 轮的内层恰好执行 $i$ 次常数成本操作，则总次数为 $1+2+\cdots +n=n(n+1)/2\in \mathrm{\Theta }(n^2)$。两个循环嵌套并不是二次界的证明：若第 $i$ 轮只执行常数次，总成本便是线性；若内层变量每轮翻倍，总次数又由对数决定。先数实际执行的操作，再用渐近记号简化，才能保留算法机制。

渐近函数也未必两两可比。令 $f(n)$ 在偶数时为 $n$、奇数时为 $n^3$，并令 $g(n)=n^2$。比值沿偶数趋于零、沿奇数趋于无穷，因此既没有 $f\in O(g)$，也没有 $f\in \mathrm{\Omega }(g)$。常见增长率表是重要例子，并不是所有资源函数构成的全序表。

渐近记号为时间理路时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。、空间理路空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。和摊还成本理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。提供统一的增长率语言，但它不会替分析者选择资源模型。最坏、期望、高概率和摊还是不同的量化维度；即使它们都得到 $O(n)$，结论也不相同。通信位数、oracle 查询次数与机器指令同样不能只因量纲都写成一个整数就直接比较。

多参数界应保留真正会变化的参数，并说明趋近区域。比如

可以表示存在与 $n,\epsilon$ 均无关的 $c,n_0$，使定理规定范围内的所有 $n\ge n_0$、$0<\epsilon \le {\epsilon }_0$ 都满足该界；也可能只表示固定 $\epsilon$ 后关于 $n$ 的上界，此时隐藏常数允许依赖 $\epsilon$。两种陈述必须用量词、下标或文字区分。类似地，若复杂度还依赖字长、块大小、输出大小或错误概率，省略参数只在它已被明确固定时才安全。

因此，“某问题需要 $\mathrm{\Omega }(n)$”必须同时交代 $n$ 表示什么、计算单位是什么、其他参数如何量化。对多变量函数也没有唯一的“趋于无穷”：可以要求各坐标独立增长，也可以限定在 $m\le n^2$ 之类的区域内。定义域和常数依赖关系都是渐近结论的一部分，而不是排版细节。