Trong hướng dẫn này, bạn sẽ học các ký hiệu tiệm cận là gì. Ngoài ra, bạn sẽ tìm hiểu về ký hiệu Big-O, ký hiệu Theta và ký hiệu Omega.
Hiệu quả của một thuật toán phụ thuộc vào lượng thời gian, dung lượng lưu trữ và các tài nguyên khác cần thiết để thực thi thuật toán. Hiệu quả được đo với sự trợ giúp của các ký hiệu tiệm cận.
Một thuật toán có thể không có cùng hiệu suất cho các loại đầu vào khác nhau. Với việc tăng kích thước đầu vào, hiệu suất sẽ thay đổi.
Nghiên cứu sự thay đổi trong hiệu suất của thuật toán với sự thay đổi thứ tự của kích thước đầu vào được định nghĩa là phân tích tiệm cận.
Ký hiệu tiệm cận
Ký hiệu tiệm cận là các ký hiệu toán học được sử dụng để mô tả thời gian chạy của một thuật toán khi đầu vào có xu hướng hướng tới một giá trị cụ thể hoặc một giá trị giới hạn.
Ví dụ: Trong sắp xếp bong bóng, khi mảng đầu vào đã được sắp xếp, thời gian thực hiện của thuật toán là tuyến tính tức là trường hợp tốt nhất.
Nhưng, khi mảng đầu vào ở điều kiện ngược lại, thuật toán sẽ mất thời gian tối đa (bậc hai) để sắp xếp các phần tử tức là trường hợp xấu nhất.
Khi mảng đầu vào không được sắp xếp hoặc theo thứ tự ngược lại, thì nó sẽ mất thời gian trung bình. Các khoảng thời gian này được biểu thị bằng ký hiệu tiệm cận.
Chủ yếu có ba ký hiệu tiệm cận:
- Ký hiệu Big-O
- Ký hiệu Omega
- Ký hiệu Theta
Ký hiệu Big-O (ký hiệu O)
Ký hiệu Big-O đại diện cho giới hạn trên của thời gian chạy của một thuật toán. Do đó, nó đưa ra độ phức tạp trong trường hợp xấu nhất của một thuật toán.
Big-O cung cấp giới hạn trên của một hàm
O (g (n)) = (f (n): tồn tại các hằng số dương c và n 0 sao cho 0 ≦ f (n) ≦ cg (n) với mọi n ≧ n 0 )
Biểu thức trên có thể được mô tả như một hàm f(n)thuộc tập hợp O(g(n))nếu tồn tại một hằng số dương csao cho nó nằm giữa 0và cg(n), cho đủ lớn n.
Đối với bất kỳ giá trị nào của n, thời gian chạy của một thuật toán không vượt qua thời gian được cung cấp bởi O(g(n)).
Vì nó cung cấp thời gian chạy trong trường hợp xấu nhất của một thuật toán, nó được sử dụng rộng rãi để phân tích một thuật toán vì chúng ta luôn quan tâm đến trường hợp xấu nhất.
Ký hiệu Omega (ký hiệu Ω)
Ký hiệu Omega đại diện cho giới hạn dưới của thời gian chạy của một thuật toán. Do đó, nó cung cấp độ phức tạp trường hợp tốt nhất của một thuật toán.
Omega cung cấp giới hạn dưới của một hàm
Ω (g (n)) = (f (n): tồn tại các hằng số dương c và n 0 sao cho 0 ≦ cg (n) ≦ f (n) với mọi n ≧ n 0 )
Biểu thức trên có thể được mô tả như một hàm f(n)thuộc tập hợp Ω(g(n))nếu tồn tại một hằng số dương csao cho nó nằm trên cg(n), cho đủ lớn n.
Đối với bất kỳ giá trị nào của n, thời gian tối thiểu theo yêu cầu của thuật toán là do Omega đưa ra Ω(g(n)).
Ký hiệu Theta (ký hiệu Θ)
Ký hiệu Theta bao quanh hàm từ bên trên và bên dưới. Vì nó đại diện cho giới hạn trên và giới hạn dưới của thời gian chạy của một thuật toán, nó được sử dụng để phân tích độ phức tạp trong trường hợp trung bình của một thuật toán.
Theta giới hạn hàm trong các yếu tố hằng số
Đối với một hàm g(n), Θ(g(n))được cho bởi quan hệ:
Θ (g (n)) = (f (n): tồn tại các 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 )
Biểu thức trên có thể được mô tả như một hàm f(n)thuộc tập hợp Θ(g(n))nếu tồn tại các hằng số dương và sao cho nó có thể được kẹp giữa và , cho n đủ lớn.c1c2c1g(n)c2g(n)
Nếu một hàm f(n)nằm ở bất kỳ vị trí nào giữa và cho tất cả , thì được cho là bị ràng buộc chặt chẽ về mặt tiệm cận.c1g(n)c2g(n)n ≧ n0f(n)
