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 Omega lớn
Ký hiệu Big-Omega (Ω) cung cấp giới hạn dưới cho một hàm f (n) trong một hệ số không đổi.
Chúng ta viết f (n) =Ω (g (n)), Nếu có các hằng số dương n0 và c sao cho, ở bên phải của n 0 f (n) luôn nằm trên hoặc trên c * g (n).
Ω (g (n)) ={f (n):Tồn tại hằng số dương c và n0 sao cho 0 ≤ c g (n) ≤ f (n), với mọi n ≤ n 0 }
Ký hiệu Theta lớn
Ký hiệu Big-Theta (Θ) cung cấp giới hạn cho một hàm f (n) trong một hệ số không đổi.
Chúng ta viết f (n) =Θ (g (n)), Nếu có các hằng số dương n0 và c 1 và c 2 sao cho ở bên phải của n 0 f (n) luôn nằm giữa c 1 * g (n) và c 2 * g (n) bao gồm.
Θ (g (n)) ={f (n):Tồn tại hằng số dương c 1 , c 2 và n 0 sao cho 0 ≤ c 1 g (n) ≤ f (n) ≤ c 2 g (n), với mọi n ≥ n 0 }
