關於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}這一事實得出。）