Groß-O in LaTeX (O(n))

Verwendung

Asymptotische obere Schranke: f(n) = O(n) bedeutet, dass f für große n nicht schneller wächst als ein konstantes Vielfaches von n.

Groß-O ist das Arbeitspferd der Algorithmenanalyse: Lineare Suche läuft in O(n), Mergesort in O(n \log n), naive Matrixmultiplikation in O(n^3). Genau genommen ist O(g) eine Menge von Funktionen, f \in O(g) ist also die präzise Form, auch wenn f(n) = O(g(n)) die nahezu universelle Konvention ist. Manche Autoren bevorzugen ein kalligrafisches \mathcal{O}(n), um den Operator von einer Variablen namens O zu unterscheiden; entscheiden Sie sich für eine Variante und bleiben Sie in der ganzen Arbeit dabei. Schreiben Sie das Argument mit den tatsächlichen Kosten im Inneren, etwa O(n^2 \log n) statt O(n^2) \cdot \log n, und denken Sie daran, dass O nur nach oben beschränkt und daher nicht behauptet, die Schranke sei scharf.

Minimales kompilierbares Beispiel

Fügen Sie dies in eine leere .tex-Datei ein und kompilieren Sie mit pdfLaTeX, XeLaTeX oder 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}

Verwandte Symbole

• Groß-Omega\Omega(n)
• Groß-Theta\Theta(n)
• Klein-oo(n)
• Klein-Omega\omega(n)
• Abbildungspfeil\mapsto
• Definitionszeichen:=

Häufige Fragen

Wie schreibe ich Groß-O in LaTeX?

Schreiben Sie O(n) im Mathematikmodus, zum Beispiel $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$. Es funktioniert in Standard-LaTeX, ohne ein Paket zu laden.

Welches Paket brauche ich für O(n)?

Keines. O(n) gehört zum Standardumfang von LaTeX und kompiliert ohne weitere Angaben in der Präambel außer der Dokumentklasse.

Kann ich O(n) im Textmodus verwenden oder nur im Mathematikmodus?

Beides. O(n) kompiliert im Fließtext ebenso wie innerhalb von $...$; in einer Formel bleibt es im Mathematikmodus, damit es mathematische Schriften und Abstände erhält.