Kí hiệu tiệm cận
Các ký hiệu tiệm cận được sử dụng để biểu thị sự phức tạp của các thuật toán để phân tích tiệm cận. Các ký hiệu này là công cụ toán học để biểu diễn sự phức tạp. Có ba ký hiệu thường được sử dụng.
Ký hiệu Big Oh
Ký hiệu Big-Oh (O) đưa ra giới hạn trên cho một hàm f (n) trong một hệ số không đổi.
Ta viết f (n) =O (g (n)), Nếu tồn tại các hằng số dương n0 và c sao cho, ở bên phải n0 thì f (n) luôn nằm trên hoặc dưới c * g (n).
O (g (n)) ={f (n):Tồn tại hằng số dương c và n0 sao cho 0 ≤ f (n) ≤ c g (n), với mọi n ≤ n0}
