Cho tui hỏi là big O của biểu thức F(n) = log(n) + 1000000 có phải là O(1).
Tìm big O cùa biểu thức
đúng rồi đấy bạn…
Sao O(1) được 
có log(n) kìa.
4 Likes
Khó khăn ở cái log(n) đó bác. Ví dụ n là 10^1000000 là một triệu số 0, con số lớn đến chừng nào, với thực tế chả khi nào đến được con số đó thì giá trị biểu thức luôn sấp sĩ 1000000, nên tui nghĩ nó là O(1).
Cứ lấy định nghĩa ra thôi F(n) \notin O(1) (sẽ lớn hơn bất kì hằng số nào).
Ý nghĩa của big-O là xét mức tăng theo một đặc điểm nào đó. O(1) nghĩa là dù n tăng thì F(n) cũng không tăng theo.
3 Likes
Nó là O(log n) bạn, cái log(n) là nằm trong thang đo BigO rồi, ko phân giải ra được nữa, còn + 1000000 là constant nên bỏ được (dùng quy tắc lấy max)
Bạn tham khảo thang BigO Notation ở đây https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?