渐近记号

常数 $c$ 吸收机器、语言与实现的固定倍率差异，起点 $n_0$ 则忽略有限多个小输入上的反常。这使比较聚焦于输入放大时成本如何增长，得到 $\log n\prec n\prec n\log n\prec n^2\prec 2^n$ 这类结构性层次。$O(g)$ 只是上界函数类，紧确的同阶结论应写成 $\mathrm{\Theta }(g)$。

$3n^2+5n+7\in \mathrm{\Theta }(n^2)$：当 $n\ge 1$ 时，$3n^2\le 3n^2+5n+7\le 15n^2$。换底公式说明 ${\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)$ 实现。渐近优势只是“最终”的承诺，现实输入仍受常数、内存层次和实现成本影响。

渐近记号为时间公理库时间复杂度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$ 之类的区域内。定义域和常数依赖关系都是渐近结论的一部分，而不是排版细节。