Ký hiệu O lớn

Trong toán học, ký hiệu O lớn dùng để chỉ hành vi giới hạn của một hàm số khi đối số tiến đến một giá trị nhất định hoặc vô cùng. Trong khoa học máy tính, ký hiệu O lớn dùng để mô tả hành vi thuật toán (ví dụ, về mặt thời gian tính toán hoặc lượng bộ nhớ cần dùng) khi kích thước dữ liệu thay đổi.

Ký hiệu O lớn mô tả các hàm theo tốc độ tăng của chúng: các hàm khác nhau có cùng tốc độ tăng có thể được mô tả bởi cùng một ký hiệu O lớn. Mô tả hàm bằng ký hiệu O lớn thường chỉ cung cấp một chặn trên cho tốc độ tăng của hàm. Bên cạnh ký hiệu O lớn còn có các ký hiệu liên quan khác, sử dụng các ký hiệu o, Ω, ω, và Θ, để mô tả các chặn khác cho tốc độ tăng.

Ký hiệu O lớn cũng được sử dụng trong nhiều ngành khác để cung cấp những ước lượng tương tự.

Định nghĩa

Giả sử f(x) và g(x) là hai hàm số định nghĩa trên tập số thực. Ta viết

f(x)=O(g(x)){\mbox{ khi }}x\to \infty \,

khi và chỉ khi tồn tại một hằng số M khác 0 sao cho với mọi giá trị đủ lớn của x, f(x) nhỏ hơn M lần g(x) về giá trị tuyệt đối. Có nghĩa là, f(x) = O(g(x)) khi và chỉ khi tồn tại số thực dương M và số thực x₀ sao cho

|f(x)|\leq \;M|g(x)|\quad \forall x>x_{0}.

Trong nhiều trường hợp, giả thiết x tiến đến vô cùng là ngầm hiểu, và ta chỉ cần viết f(x) = O(g(x)). Ký hiệu này cũng có thể dùng để mô tả giá trị của f xung quanh giá trị a (thông thường, a = 0): ta nói

f(x)=O(g(x)){\mbox{ khi }}x\to a\,

khi và chỉ khi tồn tại các số thực dương δ và M sao cho

|f(x)|\leq \;M|g(x)|{\mbox{ khi }}|x-a|<\delta .

Nếu g(x) là khác không khi x đủ gần a, cả hai định nghĩa đều có thể được viết bằng giới hạn trên:

f(x)=O(g(x)){\mbox{ khi }}x\to a\,

khi và chỉ khi

\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .

Ký hiệu o nhỏ

Ta viết

$f(x)=o(g(x))$ khi $x\to \infty$

nếu $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ .

Lịch sử

Ký hiệu này được đưa ra đầu tiên bởi nhà nghiên cứu lý thuyết số Paul Bachmann năm 1894, trong phần 2 của cuốn sách Analytische Zahlentheorie ("lý thuyết số giải tích") của ông, phần 1 của cuốn sách đó (chưa có ký hiệu O lớn) xuất bản năm 1892.^[1] Ký hiệu này được phổ biến rộng rãi bởi công trình của nhà nghiên cứu lý thuyết số Edmund Landau, nên nó đôi khi được gọi là ký hiệu Landau. Trong khoa học máy tính, nó được phổ biến bởi Donald Knuth, người cũng phổ biến các ký hiệu liên quan Ω và Θ.^[2] Ông cũng ghi nhận ký hiệu Ω được đưa ra bởi Hardy và Littlewood^[3] với một ý nghĩa hơi khác và đề xuất việc sử dụng định nghĩa hiện nay. Ký hiệu của Hardy là (biểu diễn theo ký hiệu O hiện nay)

f\lesssim g\iff f\in O(g)

và

f\ll g\iff f\in o(g);

các ký hiệu tương tự cũng đôi khi được sử dụng, chẳng hạn $\preceq$ và $\prec \!\!\!\!\!\!\!\!\prec$ . Ký hiệu O lớn, đại diện cho cụm từ tiếng Anh "order of", ban đầu được ký hiệu bởi chữ hoa omicron. Ngày nay thay vào đó, chữ cái Latin hoa O có hình dạng giống hệt được sử dụng, nhưng chưa bao giờ dùng chữ số không.

Ghi chú

^ Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6, p. 25
^ Donald Knuth. Big Omicron and big Omega and big Theta, ACM SIGACT News, Volume 8, Issue 2, 1976.
^ G. H. Hardy và J. E. Littlewood, Some problems of Diophantine approximation, Acta Mathematica 37 (1914), p. 225