В примечании с большим номером O((log n)^k) = O(log n), где k - некоторая константа (например, число логарифмических для циклов), истина?Big Oh Notation O ((log n)^k) = O (log n)?
Мне сказал мой профессор, что это утверждение верно, однако он сказал, что это будет доказано позже в ходе курса. Мне было интересно, сможет ли кто-нибудь из вас продемонстрировать свою юридическую силу или иметь ссылку, где я мог бы подтвердить, верно ли это.
(1) Верно, что O (log (n^k)) = O (log n).
(2) Неверно, что O (log^k (n)) (также записывается O ((log n)^k)) = O (log n).
Наблюдение: (1) было доказано nmjohn.
Упражнение: доказать (2). (Подсказка: f (n) = log^2 n - O (log^2 n). О O (log n)? Что такое достаточно большая константа c, что для всех n, больших n0, c log n > войти^2 п)
EDIT:
на соответствующую записку, любой, кто считает этот вопрос полезным и/или интересным должен пойти проявить любовь к новой StackExchange сайта «Computer Science». Вот ссылка. Иди, сделай это новое место реальностью!
+1. Хорошая реклама сайта CS :) – helios
Вы уверены, что он не имел в виду O (log n^k), потому что это равно O (k * log n) = k * O (log n) = O (log n).
проблема была 2 логарифмической для циклов, и он явно помещал скобки там, чтобы указать, что k применяется ко всему журналу – user1084113
O (log n) - это класс функций. Вы не можете выполнять вычисления, такие как^k на нем. Таким образом, термин O (log n)^k даже не выглядит разумным для меня.
Вложенная логарифмическая для петель – user1084113
-1. Это комментарий, а не ответ. – Patrick87
Лучше спросите об этом на http://math.stackexchange.com –
Что такое _K_? Постоянная? Другой параметр, описывающий размер проблемы? Если _k_ применяется ко всему логарифму, вы намеревались написать O ((log_n_)^_k_)? –
Сделанные изменения, k - постоянная. – user1084113