algorithm - 排序时间复杂度

Question

给定以下复杂性列表:

n^(log log(n) )  ;2^n  ;3^n  ;n! ;  n^3  ;1/n  ;(n+1)!  ;  4^log(n)   ;n^2  

n^log(n)   ;log(n!)  ;nln(n)  ;  log(2^n )=nlog2 ;(log(2) )^n  ;5n^2+6  ;  n^log(n!) 

我需要按类别对它们进行排序。

我按照以下顺序对其中的一部分进行了排序，但我仍然遗漏了一些:

(n+1)!  
n!
3^n
2^n
(3/2)^n
(log(n))^log(n) =n^log(log(n) ) 
n^3
n^2 = 4*log(n) = 4^log(n) 
5n^2+6 = Θ(n^2 )
log(n!) = Θ(n*log(n))
nlog(2) = log(2^n )

我需要把剩下的放在哪里:

n^log(n)  ;  n*ln(n) ; (log(2))^n ; n^[log(n!)] ; 1/n ; 

?

而且，我如何将它们划分为公共(public)类？

如果有任何帮助，我将不胜感激

问候

Answer 1

到目前为止你做得很好。由于这是作业，我不会给出确切的答案，只会提示你遗漏的那些:

• n^log(n):这比 (log(n))^(log(n)) 增长得更快，但没那么快作为指数。您可以通过比较这三个表达式的 log 来确认这一点。

• n*ln(n):ln(n) 是 ln(10)log(n)。一般来说，log a in base c，等于 log a in base b 乘以 log b in base c。

• (log(2))^n:这是一个以 log(2) 为底的指数，约为 0.3。这几乎是 (3.333^-n) 呈指数下降。

• n^[log(n!)]:log(n!) 是 O(nlog(n)) .这意味着 n^(log(n!)) 是 O(n^n * n^log(n))

• 1/n:这是 n^(-1)，其值缓慢减小。