Dạ xin chào anh/chị.
Em đang làm bài về đánh giá big-O nhưng kết quả của em lại khác với sách, anh chị xem giúp em có phải em đang làm sai chỗ nào không ạ.
Đề + giải của sách:
Đây là phần em làm, em ra O(n^3):
Phần lý thuyết:
logn = n ???
Dạ em đọc ở mấy ví dụ trước của sách họ cho thế này nên em dùng luôn, logn là O(n) (em chưa chứng minh được n < 2^n)
O(n^3) cũng… đúng nhưng nó không chặt. Thực ra người ta hỏi Big-O nhưng luôn muốn bạn trả lời bằng Big-Theta thôi.
Anh ơi cho em hỏi, như phần giải của sách có phải: logn < 2logn với n > 1 nên logn là O(logn) đúng không anh. (cái này là Big-Theta như anh nói phải không anh, em nãy giờ search gg Big-Theta mà chưa hiểu lắm, có gì em nói sai anh bỏ qua cho em hehe)
Vì \log n \leq \log n nên \log n = O(\log n)
Do \log n \geq \log n nên \log n = \Omega(\log n)
hợp lại thành \log n = \Theta(\log n).
Ồ, em hiểu rồi, cảm ơn anh đã chỉ cho em phần big-Theta này.
Em cảm ơn anh Kisuluoibieng và anh Rogp10 đã giúp em ạ.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?
