Big-O hay còn là giới hạn trên của một hàm nào đó.
Ta nói f(x) có giới hạn trên là g(x) (hay f(x) is O(g(x))) khi sau một con số x đủ lớn thì c.g(x) luôn lớn hơn f(x), trong đó c là một con số nào đó.
Còn big-Omega thì đơn giản là ngược lại, nếu g(x) là big-O của f(x) thì f(x) là big-Omega của g(x).
Khi big-Omega bằng big-O thì nó là big-theta.
Cách dễ nhất để tìm big-O là dựa vào biểu đồ 1 < log(x) < n < n.log(n) < x^2 < 2^x < n!
VD: Xét f(x) = n.log(n)
Để tìm big-O thì là lấy những họ hàm nằm trên nó, còn tìm big-Omega thì lấy những họ hàm nằm phía dưới nó.
Có nghĩa là
n.log(n) is O(n.log(n))
n.log(n) is O(x^2)
n.log(n) is O(x^3)
…
n.log(n) is Ω(n.log(n))
n.log(n) is Ω(n)
n.log(n) is Ω(log(n))
…
n.log(n) is Θ (n.log(n))
Cách tính độ phức tạp của một số giải thuật đơn giản. QUY TẮC XÁC ĐỊNH ĐỘ PHỨC TẠP • Read more
1. Giới thiệu Đối với một người làm về khoa học máy tính, thuật toán chắc chắn phải là một Read more
Trong danh sách liên kết bình thường, chúng ta sẽ duyệt qua danh sách này từ node đầu tiên là Read more
Danh sách liên kết đôi (Doubly Linked List): Mỗi node trong danh sách liên kết đôi gồm có previous pointer, Read more
Để lại một phản hồi
Bạn phải đăng nhập để gửi phản hồi.