Ký hiệu O lớn trong LaTeX (O(n))

Dùng ở đâu

Cận trên tiệm cận: f(n) = O(n) nghĩa là f tăng không nhanh hơn một hằng số nhân với n khi n đủ lớn.

O lớn là công cụ chủ lực của phân tích thuật toán: tìm kiếm tuyến tính chạy trong O(n), sắp xếp trộn trong O(n \log n), nhân ma trận thông thường trong O(n^3). Nói chặt chẽ, O(g) là một tập hợp hàm, nên f \in O(g) là cách viết chính xác, dù f(n) = O(g(n)) là quy ước gần như phổ quát. Một số tác giả thích dùng chữ viết tay \mathcal{O}(n) để phân biệt toán tử với một biến tên O; hãy chọn một cách và giữ nhất quán trong toàn bài. Hãy đặt toàn bộ chi phí thực vào trong đối số, như O(n^2 \log n), thay vì O(n^2) \cdot \log n, và nhớ rằng O chỉ chặn từ phía trên, nên nó không khẳng định cận là chặt.

Ví dụ tối giản biên dịch được

Dán đoạn này vào một tệp .tex trống rồi biên dịch bằng pdfLaTeX, XeLaTeX hoặc 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}

Ký hiệu liên quan

• Ký hiệu Omega lớn\Omega(n)
• Ký hiệu Theta lớn\Theta(n)
• Ký hiệu o nhỏo(n)
• Ký hiệu omega nhỏ\omega(n)
• Mũi tên ánh xạ\mapsto
• Dấu định nghĩa hai chấm bằng:=

Câu hỏi thường gặp

Làm thế nào để viết Ký hiệu O lớn trong LaTeX?

Gõ O(n) trong chế độ toán, ví dụ $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$. Lệnh dùng được trong LaTeX chuẩn mà không cần nạp gói nào.

Cần gói nào để dùng O(n)?

Không cần gói nào. O(n) thuộc LaTeX chuẩn, nên chỉ cần lớp tài liệu trong phần mở đầu là biên dịch được.

Có thể dùng O(n) trong chế độ văn bản không, hay chỉ trong chế độ toán?

Cả hai. O(n) biên dịch được trong văn bản lẫn bên trong $...$; trong công thức hãy để nó ở chế độ toán để dùng phông chữ và khoảng cách toán học.