(log (n)) ^ log (n) и n / log (n), что быстрее?

Question

f(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))

Answer 1

Возьмите бревно с обеих сторон:

log (f (n)) = log (log n) * log n

log (g (n)) = log (n) - log (log (n)) = log (n) (1 - log (log (n)) / log (n))

Ясно, что log (log (n)) доминирует (1 - log (log (n)) / log (n)), поэтому g является O (f). е не O (г). Поскольку это домашнее задание, вам может потребоваться заполнить детали.

Также довольно легко понять, каким должен быть ответ, просто попробовав его с большим числом. 1024 равно 2 ^ 10, поэтому, принимая n = 1024:

f (n) = 10 ^ 10

г (н) = 1024 / 10.

Очевидно, что это не доказательство, но я думаю, что мы можем видеть, кто победит в этой гонке.

Answer 2

f (n) растет быстрее, чем g (n) тогда и только тогда, когда f (e ⁿ ) также растет быстрее чем g (e ⁿ ) , поскольку exp строго увеличивается до бесконечности (докажите это самостоятельно).

Сейчас f (e ⁿ ) = n ⁿ и g (e ⁿ ) = e ⁿ / n , и вы можете процитировать известные результаты.

Answer 3

f значительно больше. По n^loglog(n) -1 . log n

Answer 4

Mathematica дает предел f(n) / g(n), когда n стремится к бесконечности как бесконечность, что означает, что f растет быстрее. Это означает, что g(n) belongs to (=) O(f(n)).

Вы можете использовать это , например, если у вас нет Mathematica.

Answer 5

Если предел [f [x] / g [x], x -> Infinity] = бесконечность, то f [x] растет быстрее, чем g [x].

Предел [Log [x] ^ Log [x] / (x / Log [x]), x -> Бесконечность] = + Бесконечность

Итак, Log [x] ^ Log [x] растет быстрее, чем x / Log [x]