Big O notation là gì?

Ký hiệu Big O (Big O notation) là một cách thuận tiện để mô tả một hàm (function) đang tăng trưởng nhanh như thế nào.

Khi chúng ta tính toán độ phức tạp thời gian T (n) (time complexity) của một thuật toán (algorithm ), chúng ta hiếm khi nhận được kết quả chính xác chỉ là một ước tính. Do đó trong khoa học máy tính (computer science) chúng ta thường chỉ quan tâm đến tốc độ tăng triển của T (n) dưới dạng một hàm của kích thước đầu vào n.

Ví dụ nếu một thuật toán tăng từng số thêm 1 (increment) trong danh sách (list) có độ dài n, chúng ta có thể nói: “Thuật toán này chạy trong thời gian O (n) và thực hiện công việc O (1) cho mỗi phần tử (element)”.

Đây là định nghĩa toán học chính thức của Big O.

Gọi T (n) và f (n) là hai hàm số dương (positive function). Ta viết T (n) ∊ O (f (n)), và nói rằng T (n) có bậc là f (n), nếu có các hằng số dương M và n₀ sao cho T (n) ≤ M · f (n ) với mọi n ≥ n₀.

Biểu đồ này cho thấy một tình huống mà tất cả các điều kiện trong định nghĩa được đáp ứng.

Về bản chất: T (n) ∊ O (f (n)) có nghĩa là T (n) không tăng trưởng nhanh hơn f (n).