LaTeX 中的大 O 记号（O(n)）

用途

渐近上界：f(n) = O(n) 表示当 n 足够大时，f 的增长不快于 n 的某个常数倍。

大 O 是算法分析的主力工具：线性查找的运行时间为 O(n)，归并排序为 O(n \log n)，朴素矩阵乘法为 O(n^3)。严格来说，O(g) 是一个函数集合，因此 f \in O(g) 才是精确写法，不过 f(n) = O(g(n)) 几乎是通用约定。有些作者偏好花体的 \mathcal{O}(n)，以便把该运算符与名为 O 的变量区分开；请选定一种，并在整篇论文中保持一致。把真实的代价写在括号内，如 O(n^2 \log n)，而不要写成 O(n^2) \cdot \log n；并且记住 O 只给出上界，并不断言该上界是紧的。

最小可编译示例

将其粘贴到空白 .tex 文件中，用 pdfLaTeX、XeLaTeX 或 LuaLaTeX 编译。

\documentclass{article}
\usepackage{amsmath}
\begin{document}
Big O: $O(n)$

\[ T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n) \]
\end{document}

相关符号

• 大 Ω 记号\Omega(n)
• 大 Θ 记号\Theta(n)
• 小 o 记号o(n)
• 小 ω 记号\omega(n)
• 映射箭头\mapsto
• 定义等号:=

常见问题

如何在 LaTeX 中输入大 O 记号？

在数学模式中输入 O(n)，例如 $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$。无需加载任何宏包即可在标准 LaTeX 中使用。

O(n) 需要哪个宏包？

不需要。O(n) 是标准 LaTeX 的一部分，导言区只需文档类即可编译。

O(n) 能在文本模式中使用，还是只能用于数学模式？

两者皆可。O(n) 在正文和 $...$ 中都能编译；在公式中请保持数学模式，以获得数学字体和间距。