Kí hiệu O lớn

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

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ố đủ lớn M 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 x0 sao cho

|f(x)| \le \; 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 δM sao cho

|f(x)| \le \; 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.

Lịch sử[sửa | sửa mã nguồn]

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\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ú[sửa | sửa mã nguồn]

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