O（nⁿ）和O的時間複雜度

Question

獲取以下

O(1), O(log(n)), O(n⋅log(n)),O(n), O(n²), O(2ⁿ), O(n!), O(nⁿ), O(n³). 

順序應該是下面的複雜性順序：

O(1) < O(log(n)) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(nⁿ) < O(n!) 

在我看來，nⁿ= N ⋅n⋅n⋅...
然而，n! = n(n-1)(n-2).....所以O(n!) < O(nⁿ)

然而，另一位朋友說：O(nⁿ) < O(n!)，

因爲n! = sqrt(2πn) ⋅ (n/e)ⁿ

我不知道如何得到這個，請詳細介紹一下這個。

Answer 1

讓我們假設N是= 4

• 如果調用O（N！），循環將迭代N！每個循環的時間。第一個循環爲1，第二個循環爲1,2，第三個循環爲1,2,3，第四個循環爲1,2,3,4。
• 所以你有：
• 1,2
• 1，2，3
• 1，2，3，4
• 而且如果調用O（N^N），環路將迭代N次每次循環。第一環將是1,2,3,4第二環將是1,2,3,4第三環將是1,2,3,4並且第四環將是1,2,3,4
• 所以，你必須：
• 1，2，3，4
• 1，2，3，4
• 1，2，3，4
• 1，2，3，4
• 所以你可以看到O（N！）將比O（N^N）更早終止，因爲每次迭代都不必循環到列表的末尾。因此時間複雜度O（N！）O（N^N）或O（N！）比O（N^N）好。

Answer 2

公式n! ≈ sqrt(2πn) ⋅ (n/e)ⁿ被稱爲Stirlings approximation。
但是，這也顯示O(n!) < O(nⁿ)，如果你知道sqrt(n)增長遠低於(1/e)ⁿ下降（生長n）。 （limn → ∞ sqrt(n)/eⁿ = 0）。所以

O(n!) = O(sqrt(n) ⋅ (1/e)ⁿ ⋅ nⁿ) < O(nⁿ) 

holdes，因爲sqrt(n) ⋅ (1/e)ⁿ得到遠小於1，在O((1/e)ⁿ)順序。

但該公式只是一個近似值。如您所述：

nⁿ = n ⋅ n ⋅ ... ⋅ n (n times) 
n! = n ⋅ (n-1) ⋅ ... ⋅ 2 ⋅ 1 
    < n ⋅ n ⋅ ... ⋅ n = nⁿ 

這足以證明O(n!) < O(nⁿ)。