Big O trong toán rời rạc (Discrete Math)

algorithm

(Ga Mat Ong) #1

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 ạ?


(rogp10) #2

Dịch từng chữ :smiley: 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 :smiley: )
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.

  • “sup” là để sin(n) = O(1).
  • Ngoài ra 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 :smiley: ) nên sin(n) = O(1).

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?