关于n阶乘的θ表示的渐近分析

Question

如果我有一个运行在log（n ^（5/4）！）时间的算法，我怎么能把它表示为log（n）？难道只是我知道log（n！）会渐进地等于nlog（n），但是（5/4）会改变什么吗？如果是这样的话？

Answer 1

好问题！正如您注意到的log(n!) = O(n log n)。由此得出结论：

log(n^{5/4}!) = O(n^{5/4} log n^{5/4}) = O(n^{5/4} log n) 

最后的等式是因为log n^{5/4} = (5/4)*log n。

因此，您可以将表达式简化为O(n^{5/4} log n)。

答案是肯定的，指数中的因子5/4很重要：函数n^{5/4}渐近地快于n，所以你不能忽略它。 （例如，这从n^{5/4}/n = n^{1/4}这一事实得出。）