Когда f (n) = n ^ .1 и g (n) = log (n) ^ 10, f (n) = Ω (g)?

Question

Мне сказали, что «любая экспонента превосходит любой логарифм».

Но когда экспонента находится между нулем и единицей, разве время выполнения логарифма не увеличивается намного быстрее?Таким образом, по этой логике было бы f = O (g)

У меня возникли проблемы с выбором, следовать ли моей интуиции или тому, что мне сказали, но то, что мне сказали, могло быть не совсемточный.

Answer 1

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

log f (x) ≤ log g (x)

, то

f (x) ≤ g (x)

Теперь давайте посмотрим, что это здесь делает.У нас есть две функции: x ^0.1 и log ¹⁰ x.Если мы возьмем их журналы, мы получим

log (x ^0.1 ) = 0,1 log x

и

log (log ¹⁰ x) = 10 log log x

Поскольку log log x растет намного медленнее, чем log x, интуитивно мы видим, что функция x ^0.1 собирается в конечном итоге обогнать журнал ¹⁰ x.

Теперь давайте формализуем это.Мы хотим найти некоторое значение x, такое, что

x ^0.1 > log ¹⁰ x

Предположим, что этиявляются логарифмами основания 10 только, чтобы сделать математику легче.Если предположить, что x = 10 ^k для некоторого k, мы получим, что

(10 ^k ) ^0.1 ≥ log ¹⁰ 10 ^k

10 ^{0.1 k} > log ¹⁰ 10 ^k

10 ^{0,1 k} > k

Теперь возьмем k = 100. Теперь у нас есть

10 ^{0,1 * 100} > 100

10 ¹⁰ > 100

, что совершенно верно.Поскольку обе функции монотонно растут, это означает, что для x ≥ 10 ¹⁰⁰ верно, что

x ^0.1 > log ¹⁰ x

Это означает, что не верно, что x ^0,1 = O (log ¹⁰ k).

Надеюсь, это поможет!

Answer 2

Асимптотический анализ действительно сфокусирован на долгосрочных отношениях (так как n предполагает большие значения, как сравниваются значения функций)? Он также игнорирует константы, поэтому иногда вы видите странные ситуации, такие как f (x) = 10000000 * x = O (x ^ 2).

Для больших значений n, f(n) > g(n), что действительно важно.

Answer 3

Еще один способ убедиться, что n^0.1 = big omega(log^10(n)) с помощью правила ограничения?

Правило лимита:

предел как n-> бесконечность f (n) / г (г).

если предел равен положительной бесконечности, f (n)! = O (g (n)) & g (n) = O (f (n)) или f (n) = большая омега (g (n))

если предел равен 0, f (n) = O (g (n)) & g (n)! = O (f (n))

если предел является положительным действительным числом, f (n) = O (g (n)) & g (n) = O (f (n)) или f (n) = большая тета (g (n) )

Для этой проблемы:

пусть f (n) = O (n ^ 0.1) и g (n) = log ^ 10 (n)

Это дает нам предел:

предел как n-> бесконечность (n ^ 0.1) / (log ^ 10 (n))

Используя правило L'Hospital's на лимите 10 раз, мы получим:

предел как n-> бесконечность ((0,1) ^ 10 * ln ^ 10 (b) * n ^ 0,1) / (10!) Где b - основание бревна

Поскольку n-член входит только в числитель, предел приближается к бесконечности.

По правилу лимита

log ^ 10 (n) = O (n ^ 0.1) & n ^ 0.1! = O (log ^ 10 (n) или n ^ 0.1 = большая омега (log ^ 10 (n)).