Как мы можем развернуть (logn)! и (logn!)! определить сложности?

Question

Я знаю, что log n! дает сложность O (nlogn), но как exapnd выше? Второй может быть упрощен до (nlogn) !. Просьба пояснить это.

Answer 1

Обновление: Нет, вы не можете использовать (N ln N)! в своей второй формуле. Причина объясняется ниже, используя первый случай.

С log version of Stirling approximation мы имеем

ln(z!) = (z+1/2) ln z - z + O(1)... 

Обратите внимание, что дополнительный z хранятся здесь, причина будет очевидно, в ближайшее время. Теперь, если мы позволим x = log N,

(ln N)! = x! = exp(ln x!) 
~ exp((x+1/2) ln x - x) = x^(x+1/2) exp(-x) 
= (ln N)^((ln N)+1/2)/N 

Дополнительный срок мы постоянно оказывается быть обратным N, это, безусловно, оказывает влияние на сложность, так как мы не можем просто выбросить ехр чего-то. Если мы обозначим g(N) для приближения выше и f(N) = (ln N)!, то lim f(N)/g(N) = sqrt(2 pi) < inf, так f = O(g)

Для (ln N!)!, это немного сложнее, я использую Mathematica для проверки предела, и это говорит о том, что расширение

ln(z!) ~ (z+1/2) ln z - z + ln(sqrt(2pi)) 

достаточно. У меня нет общего правила, когда мы можем остановиться. И вообще, возможно, не удастся использовать только конечные термины. Но в этом случае мы можем.

Если вам нужна только свободная привязка, для первой формулы вы можете фактически отказаться от термина -z, потому что (z+1/2) ln z > (z+1/2) ln z - z.

Answer 2

Вы можете оценить верхнюю и нижнюю границы для (log(n))! с использованием тождества вместе с оценками продукции.

Для верхней границы:

Для нижней границы:

Комбинированные вы получите:

Так, по крайней мере:

Очевидно, что (в) уравнения как-то лишняя вследствие нецелая индекса границ продукты.

Обновление: Связанные дается hwlau с использованием стерлингового приближения ниже (sqrt(log(n))/n) и должна быть жесткими.