以升序時間複雜度

Question

什麼是以下功能中的生長速率的升序：

1. 2 ^（（logn）時間^ 1/2）

2. 2^N

3. 2 ^（N/2）
4. ñ^（4/3）
5. N（logn）時間^ 3
6. N R個LOGN
7. 2 ^（n^2）

8. n！

   日誌n是與基地2

Answer 1

• 我們可以直接推斷n!是最高的順序，因爲這等於

  

  ...和n^n部分遠遠超過了其他任何功能。

• 由於

  

  我們可以推斷，（1）是小於其它功能與n作爲鹼，例如（4），（5）和（6）。其實它小於全部的其他功能。

• （3）<（2），因爲後者是前平方。

• （2）<（7），因爲後者是前者的權力n。

• （4）<（6），自log n > 4/3。

• 從this post，log n增長超過的n任何積極的力量更慢。因此：

  

  因此（5）<（4），（6）

• 使用對數定律變換，我們得到以下：

  

  因此（6 ）<（3）。

---

編譯上述所有推理步驟，我們推斷升序爲：

（1）。

（5）。

（4）。

（6）。

（3）。

（2）。

（7）。​​

（8）。