Có vấn đề thị giác à mà không thấy 2 bức hình to vậy còn bảo đưa ? Kém khả năng đọc hiểu à mà không google ra được ? Hay do học hành không tới nơi tới chốn ? Càng nói càng cùn
Big oh (O) – Worst case
Big Omega (Ω) – Best case
Big Theta (Θ) – Average case
Bạn bảo sai thì chứng minh, còn không thì đừng có cùn nữa, kém thật sự
Big O = Chặn trên. g(n) = O(f(n)) có nghĩa là tồn tại một hằng số c sao cho g(n) <= c * f(n), với n đủ lớn. Có nghĩa là một thuật toán chạy hết n^2 bước thì gọi là O(n^3) cũng không sai.
Big Theta = Kẹp giữa hai hằng số. f(n) = Theta(g(n)) có nghĩa là tồn tại hai hằng số c1 c2 sao cho c1*g(n) <= f(n) <= c2*g(n).
Big Omega = Chặn dưới bởi một hằng số.
Tốt nhất thì nên tính được Big Theta, bởi vì nó chính xác hơn. Một thuật toán Theta(n^2) thì có nghĩa là số bước thực hiện luôn là bậc 2 chứ không phải bậc khác. Lý do người ta dùng Big O nhiều hơn là vì nó dễ tính hơn. Big Theta thì không phải lúc nào cũng tính được.
Và mấy cái này chỉ là notation để ước lượng mức độ tăng trưởng của một hàm số, chả liên quan gì đến best, average hay worst hết. Không có ai cấm người ta dùng O cho average case hay Theta cho worst case.
Sent from Xiaomi Redmi 5A using vozFApp
Last edited:
