是log(n！)相当于nlogn？(大O符号) [英] is log(n!) equivalent to nlogn? (Big O notation)

问题描述

在我的书中有一道选择题：

以下函数的大O符号是什么： n^log(2)+log(n^n)+nlog(n！)

我知道该日志(n！)属于O(Nlogn)，但我在网上看到它们是等价的。log(n！)怎么样？跟说nlogn是一回事吗？ 情况如何： log(n！)=logn+log(n-1)+.+log2+log1 相当于nlogn？

推荐答案

设n/2为n除以2的商。我们有：

log(n!) =  log(n) + log(n-1) + ... + log(n/2) + log(n/2 - 1) + ... + log(2) + log(1)
        >= log(n/2) + log(n/2) + ... + log(n/2) + log(n/2 - 1) + ... + log(2)
        >= (n/2)log(n/2) + (n/2)log(2)
        >= (n/2)(log(n) -log(2) + log(2))
        =  (n/2)log(n)

然后

n log(n) <= 2log(n!) = O(log(n!))

和n log(n) = O(log(n!))。相反，

log(n!) <= log(n^n) = n log(n)

和log(n!) = O(n log(n))。

这篇关于是log(n！)相当于nlogn？(大O符号)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！