Асимптотическая сложность логарифмов и степеней
Итак, ясно, что log(n)- это O(n). Но как насчет (log(n))^2? Как насчет sqrt(n) или log(n)- что за границы?
Есть семейство сравнений, подобных этому:
п ^ а против (журнал (п)) ^ б
Я часто сталкиваюсь с этими сравнениями, и у меня никогда не было хорошего способа их решить. Советы по тактике решения общего дела?
Спасибо,
Ян
РЕДАКТИРОВАТЬ: я не говорю о вычислительной сложности вычисления значений этих функций. Я говорю о самих функциях. Например, f(n)=n является верхней границей g(n)=log(n), потому что f(n)<=c*g(n) для c=1 и n0 > 0.
3 ответа
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.
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, Там нет общего случая
Я часто сталкиваюсь с этими сравнениями (...) Советы по тактике решения общего случая?
Как вы, как о общем случае, и что вы следите много в таких вопросах. Вот что я рекомендую:
Используйте определение предела для обозначения BigO, когда вы знаете:
f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf
Вы можете использовать Систему компьютерной алгебры, например, с открытым исходным кодом Maxima, здесь в документации Maxima об ограничениях.
Для получения более подробной информации и примера - проверьте этот ответ