Ký hiệu O lớn – Wikipedia tiếng Việt

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 ) ) khi x → a { \ displaystyle 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 ) | ≤ M | g ( x ) | khi | x − a | < δ. { \ displaystyle | 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 ) ) khi x → a { \ displaystyle f ( x ) = O ( g ( x ) ) { \ mbox { khi } } x \ to a \, }

khi và chỉ khi

lim sup x → a | f ( x ) g ( x ) | < ∞. { \ displaystyle \ limsup _ { x \ to a } \ left | { \ frac { f ( x ) } { g ( x ) } } \ right | < \ infty. }

Ký hiệu o nhỏ[sửa|sửa mã nguồn]

Ta viết

f
(
x
)
=
o
(
g
(
x
)
)

{\displaystyle f(x)=o(g(x))}

khi

x
→
∞

{\displaystyle x\to \infty }

nếu

lim

x
→
∞

f
(
x
)

g
(
x
)

=
0

{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}

.

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 ≲ g ⟺ f ∈ O ( g ) { \ displaystyle f \ lesssim g \ iff f \ in O ( g ) }f ≪ g ⟺ f ∈ o ( g ) ; { \ displaystyle 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

⪯

{\displaystyle \preceq }

và

≺

≺

{\displaystyle \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.