Trong [[toán học]], '''kí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í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í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íký hiệu O lớn. Mô tả hàm bằng kí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íký hiệu O lớn còn có các kíký hiệu liên quan khác, sử dụng các kíký hiệu o, Ω, ω, và Θ, để mô tả các chặn khác cho tốc độ tăng.
Kí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==
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í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
:<math>f(x)=O(g(x))\mbox{ khi }x\to a\,</math>
==Lịch sử==
Kí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íký hiệu O lớn) xuất bản năm 1892.<ref>[[Nicholas J. Higham]], ''Handbook of writing for the mathematical sciences'', SIAM. ISBN 0-89871-420-6, p. 25</ref> Kí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í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íký hiệu liên quan Ω và Θ.<ref>Donald Knuth. ''[http://doi.acm.org/10.1145/1008328.1008329 Big Omicron and big Omega and big Theta]'', ACM SIGACT News, Volume 8, Issue 2, 1976.</ref> Ông cũng ghi nhận kíký hiệu Ω được đưa ra bởi Hardy và Littlewood<ref>[[G. H. Hardy]] và [[John Edensor Littlewood|J. E. Littlewood]], ''Some problems of Diophantine approximation,'' Acta Mathematica 37 (1914), p. 225</ref> 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íKý hiệu của Hardy là (biểu diễn theo kíký hiệu O hiện nay)
:<math> f\lesssim g \iff f \in O(g) </math> và <math> f\ll g \iff f\in o(g); </math>
các kíký hiệu tương tự cũng đôi khi được sử dụng, chẳng hạn <math>\preceq</math> và <math>\prec\!\!\!\!\!\!\!\!\prec</math>.
KíKý hiệu O lớn, đại diện cho cụm từ tiếng Anh "order of", ban đầu được kí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ố [[0 (số)|không]].
==Ghi chú==
{{Tham khảo}}
|