当前位置：网站首页>关于lg(n!)的渐进紧确界

关于lg(n!)的渐进紧确界

2022-06-21 20:39:00 【ash062】

$lg^{n!} = lg^{2} + lg^{3} + lg^{4} + lg^{5} + lg^{6} + lg^{7} +... + lg^{n}$

假设n为2的幂，且 $k = lg^{n}$

缩小等式 $lg^{n!}> lg^{2} + lg^{2} + lg^{4} + lg^{4} + lg^{4} + lg^{4} +... + lg^{n}$

记 $min = lg^{2} + lg^{2} + lg^{4} + lg^{4} + lg^{4} + lg^{4} +... + lg^{n} = \sum_{i = 1}^{k - 1}i\cdot 2^{i} + k$

进一步处理有 $min = 2min - min=(k - 1)2^{k} - \sum_{i = 1}^{k - 1}2^{i} + k=(k - 3)2^{k} + k + 2$

因此 $lg^{n!} = \Omega (nlg^{n})$

类似放大等式 $lg^{n!} < lg^{2} + lg^{4} + lg^{4} + lg^{8} + lg^{8} + lg^{8} + lg^{8} + ... + lg^{n}$

记 $max = lg^{2} + lg^{4} + lg^{4} + lg^{8} + lg^{8} + lg^{8} + lg^{8} +... + lg^{n} = \sum_{i = 1}^{k}i2^{i - 1}$

有 $max = 2max - max=k\cdot 2^{k} - \sum_{i = 1}^{k - 1}2^{i} = (k - 1)2^{k} + 2$

因此 $lg^{n!} = \bigcirc (nlg^{n})$

综上 $lg^{n!} = \Theta (nlg^{n})$

版权声明
本文为[ash062]所创，转载请带上原文链接，感谢
https://blog.csdn.net/ash062/article/details/117706127

边栏推荐

猜你喜欢

随机推荐