Асимптотическая сложность логарифмов и степеней

Question

Итак, ясно, что log (n) - это O (n).Но как насчет (log (n)) ^ 2?Как насчет sqrt (n) или log (n) - какие границы?

Существует семейство сравнений, подобных этому:n ^ a vs. (log (n)) ^ b

Я часто сталкиваюсь с этими сравнениями, и у меня никогда не было хорошего способа их решения.Советы по тактике для решения общего дела?

Спасибо,Ян

РЕДАКТИРОВАТЬ: я не говорю о вычислительной сложности вычисления значений этих функций.Я говорю о самих функциях.Например, f (n) = n является верхней границей g (n) = log (n), потому что f (n) <= c * g (n) для c = 1 и n0> 0.

Answer 1

log (n) ^ a всегда равно O (n ^ b), для любых положительных постоянных a, b.

Вы ищете доказательство? Все такие проблемы можно свести к тому, чтобы увидеть, что log (n) равно O (n), с помощью следующего трюка:

log (n) ^ a = O (n ^ b) эквивалентно: log (n) = O (n ^ {b / a}), поскольку повышение до 1 / a является возрастающей функцией. Это эквивалентно log (m ^ {a / b}) = O (m), установив m = n ^ {b / a}. Это эквивалентно log (m) = O (m), поскольку log (m ^ {a / b}) = (a / b) * log (m).

Вы можете доказать, что log (n) = O (n) по индукции, сосредоточив внимание на случае, когда n - степень 2.

Answer 2

Я часто сталкиваюсь с этими сравнениями (...) Советы по тактике решения общего дела?

Как вам общий случай и что вы много следите за такими вопросами. Вот что я рекомендую:

Используйте определение предела для обозначения BigO , когда вы знаете:

f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf

Вы можете использовать Система компьютерной алгебры , например, с открытым исходным кодом Максимум , здесь в Документация Maxima о пределах .

Для получения более подробной информации и примера - ознакомьтесь с ЭТИМ ответом

Answer 3

log n -- O(log n)
sqrt n -- O(sqrt n)
n^2 -- O(n^2)
(log n)^2 -- O((log n)^2)

n^a против (log(n))^b

Вам нужны либо базы, либо силы одинаковые. Поэтому используйте свою математику, чтобы изменить n^a на log(n)^(whatever it gets to get this base) или (whatever it gets to get this power)^b. Там нет общего случая