Em đã google trước khi hỏi nhưng em chưa hiểu chỗ này lắm ạ
Giả sử viết
3x^2 + 2x + 2 = O(x^2)
Điều này có nghĩa là gì ạ, có phải là độ phức tạp của 3x^2 + 2x + 2 khi x tiến ra vô cùng giống độ phức tạp của x^2 không ạ?
Em đã google trước khi hỏi nhưng em chưa hiểu chỗ này lắm ạ
Giả sử viết
3x^2 + 2x + 2 = O(x^2)
Điều này có nghĩa là gì ạ, có phải là độ phức tạp của 3x^2 + 2x + 2 khi x tiến ra vô cùng giống độ phức tạp của x^2 không ạ?
Dịch từng chữ O(x^2) thực chất là một tập hợp các hàm “nhỏ hơn hoặc bằng” x^2, nên viết = là không đúng, nhưng nếu viết dấu “thuộc” thì công thức sẽ phức tạp hơn (Taylor
)
Hay nói cách khác, 3x^2 + 2x + 2 “không quá cỡ” so với x^2 (big-theta là cùng một cỡ).
Big-O có một định nghĩa tương đương: f(n) = O(g(n)) <=> lim sup |f(n) / g(n)| < +inf
.
lim sup f(n) := lim (sup [n..+inf].f)
(biên trên, không phải max), mà sup(sin(n)) <= 1
(không nói == được ngay đâu sin(n) = O(1)
.