О-большое в LaTeX (O(n))

Где используется

Асимптотическая верхняя оценка: f(n) = O(n) означает, что при больших n функция f растёт не быстрее, чем n, умноженное на константу.

О-большое — основной инструмент анализа алгоритмов: линейный поиск работает за 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(n)
• омега-малое\omega(n)
• Стрелка отображения\mapsto
• Равенство по определению:=

Частые вопросы

Как написать «О-большое» в LaTeX?

Наберите 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) компилируется и в тексте, и внутри $...$; в формуле оставляйте её в математическом режиме ради математических шрифтов и интервалов.