是log(n！)相当于nlogn？(大O符号)

本文介绍了是log(n！)相当于nlogn？(大O符号)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

以下函数的大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))。