Tại sao chúng ta sử dụng Big O thay vì Big Theta (Θ)?
Tại sao chúng ta sử dụng Big O thay vì Big Theta (Θ)?
| Big-O (O) | Big-Theta (Θ) | Big-Omega (Ω) | |
|---|---|---|---|
| Ý nghĩa | Cận trên | Cận chặt (trên và dưới) | Cận dưới |
f(n) so với g(n) |
f ≤ c·g |
c₁·g ≤ f ≤ c₂·g |
f ≥ c·g |
| Ví dụ | Merge sort là O(n²) (đúng nhưng lỏng) | Merge sort là Θ(n log n) | Sắp xếp so sánh là Ω(n log n) |
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.