/codegym.vn/ - 143
Bậc Theta
Nếu tồn tại một hàm f(n) sao cho tại một giá trị n đủ lớn, thời gian thực thi của hệ
thống không lớn hơn giá trị k1.f(n) và không nhỏ hơn giá trị k2.f(n) trong đó k1 và k2
là những hằng số ,thì chúng ta nói rằng độ phức tạp thuật toán là Theta của f(n).
Bậc O-lớn
Trong một số trường hợp chúng ta không thể ước lượng được một tiệm cận dưới có
ý nghĩa thực tế. Chẳng hạn, “trong trường hợp tốt nhất, cả hai thuật toán tìm kiếm đều
chỉ mất một lần lặp để tìm được giá trị cần tìm” là một phát biểu đúng, nhưng hoàn
toàn vô nghĩa cho mục đích ước lượng độ phức tạp thuật toán. Sẽ tốt hơn nếu chúng
ta chỉ phát biểu về tiệm cận trên. Chúng ta sử dụng bậc O-lớn vào những lúc như vậy.
Nếu tồn tại một hàm f(n) sao cho tại một giá trị n đủ lớn, thời gian thực thi của hệ
thống không lớn hơn giá trị k.f(n) trong đó k là một hằng số ,thì chúng ta nói rằng độ
phức tạp thuật toán là O-lớn của f(n).
Độ phức tạp của các thuật toán tìm kiếm
Bậc O-lớn chính là mô hình tính toán thường được sử dụng để tính độ phức tạp của
thuật toán tìm kiếm tuyến tính cũng như tìm kiếm nhị phân.
Đối với thuật toán tìm kiếm tuyến tính, trên mảng có độ dài n, số vòng lặp tối đa phải
thực hiện để có thể tìm ra phần tử cần thiết chính bằng n. Tổng thời gian thực thi thuật
