performance - 时间复杂度升序

Question

以下函数的增长率的升序是什么：

1. 2^((登录)^1/2)

2. 2^n

3. 2^(n/2)
4. n^(4/3)
5. n(logn)^3
6. n^登录
7. 2^(n^2)

8. 嗯！

   log n 以 2 为底。

Answer 1

• 我们可以立即推断出n!最高阶，因为它等于

  

  ...并且该n^n部分远远超过了其他任何功能。

• 自从

  

  我们可以推断出(1) 小于其他以n(4)、(5) 和(6) 为基的函数。事实上，它比所有其他功能都少。

• (3) < (2)，因为后者是前者的平方。

• (2) < (7)，因为后者是前者的幂n。

• (4) < (6)，因为log n > 4/3.

• 从这个帖子来看，log n成长比任何正能量都 n慢。所以：

  

  因此 (5) < (4), (6)

• 使用对数定律变换，我们得到以下结果：

  

  因此 (6) < (3)。

---

编译上述所有推理步骤，我们推导出升序为：

(1)。

(5)。

(4)。

(6)。

(3)。

(2)。

(7)。

(8)。