asymptotic-complexity - 比较大的 theta 值

Question

我正在尝试从最大到最小订购这些不同的大 theta 值：

Θ(n2)
Θ(2n log n)
Θ(n log n2)
Θ(2n2)
Θ(log n)
Θ(n log 2n)
Θ(k2)
Θ(22n)
Θ(n3)
Θ(n)
Θ(2n)
Θ(n1.5)
Θ(√n)
Θ(2n2)

并且有些值是等价的。特别是，我想知道常数项是否使一个大θ值大于没有常数项的相同大θ项（例如，这两个值是否等效：Θ（22n）和Θ（n）？）。

Answer 1

Θ(log n)

Θ(√n) = Θ(n ^1/2 )

Θ(n) = Θ(2n) = Θ(22n)

Θ(n log n) = Θ(2n log n) = Θ(n log n ² ) = Θ(n log 2n)

Θ(n ^1.5 )

Θ(n ² ) = Θ(2n ² )

Θ(n ³ )

---

考虑到您的评论：

n log 2n = n (log 2 + log n) = n log 2 + n log n

log 2是一个恒定的非零值，所以：

Θ(n log 2n) = Θ(n log 2 + n log n) = Θ(n + n log n) = Θ(n log n)

查看大-{O,Theta, Omega}-符号的常数属性的总和和乘法。

Answer 2

如果尝试将 n 替换为一个巨大的值，那么您甚至无需向论坛询问就可以自己弄清楚：

o(1)
O(log log n)
O(log n)
O(n^c)
O(n)
O(n log n)
O(n^2)
O(c^n)
O(n!)