Trong ký hiệu big-O là O((log n)^k) = O(log n), trong đó k là một số hằng số (ví dụ: số logarit cho vòng lặp), đúng không?Ký hiệu Big Oh O ((log n)^k) = O (log n)?
Tôi được giáo sư của tôi nói rằng tuyên bố này là đúng, tuy nhiên, ông cho biết nó sẽ được chứng minh sau này trong khóa học. Tôi đã tự hỏi nếu bất kỳ của bạn có thể chứng minh tính hợp lệ của nó hoặc có một liên kết mà tôi có thể xác nhận nếu nó là sự thật.
(1) Đúng là O (log (n^k)) = O (log n).
(2) Giả sử O (log^k (n)) (cũng được viết O ((log n)^k)) = O (log n).
Quan sát: (1) đã được chứng minh bởi nmjohn.
Bài tập: chứng minh (2). (Gợi ý: f (n) = log^2 n là O (log^2 n) .Nó là O (log n)? Là một hằng số đủ lớn c sao cho, cho tất cả n lớn hơn n0, c log n > log^2 n)
EDIT:
Trên một lưu ý liên quan, bất cứ ai tìm thấy câu hỏi này hữu ích và/hoặc thú vị nên đi hiển thị một số tình yêu cho "Khoa học máy tính" trang web StackExchange mới. Đây là một liên kết. Hãy biến nơi này thành hiện thực!
+1. Đẹp CS trang web công khai :) – helios
Bạn có chắc chắn rằng anh ta không có nghĩa là O (log n^k), bởi vì nó bằng O (k * log n) = k * O (log n) = O (log n).
vấn đề là 2 logarit cho vòng lặp, và ông đặt một cách rõ ràng các dấu ngoặc ở đó để chỉ ra k được áp dụng cho toàn bộ log – user1084113
O (nhật ký n) là một lớp chức năng. Bạn không thể thực hiện các tính toán như^k trên đó. Do đó, thuật ngữ O (log n)^k thậm chí không hợp lý với tôi.
lôgarit lồng nhau cho các vòng – user1084113
-1. Đây là một bình luận, không phải là một câu trả lời. – Patrick87
Better hỏi này tại http://math.stackexchange.com –
_k_ là gì? Một hằng số? Một tham số khác mô tả kích thước vấn đề? Nếu _k_ được áp dụng cho toàn bộ logarit, bạn có định viết O ((log _n_)^_k_) không? –
Thay đổi được thực hiện, k là hằng số. – user1084113