Порядок роста следующей функции

Question

Может ли кто-нибудь сказать мне, правильно ли ранжирование следующих функций по порядку роста? (Увеличение к уменьшению)

2^п, п^2, (nlgn, LG (п!)), П^(1/ЛГН), 4

Answer 1

Большинство из них прав. Однако посмотрите на

n ^{1/lg n}.

Обратите внимание, что для ненулевого п, мы имеем N = 2 ^{Л.Г. н}, так что

п ^{1/Л.Г. п} = (2 ^{Л.Г. п}) ^{1/Л.Г. п} = 2 ^{Л.Г. п/п Л.Г.} = 2 = 2.

Таким образом, хотя 2 и 4 растут с одинаковой (несуществующей) скоростью, n ^{1/lg n} всегда меньше 4 для любого ненулевого n.