Сортировка временных сложностей

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 ; 

И как я могу разделить их на общие классы?

Буду признателен за любую помощь

С уважением

Answer 1

Мой окончательный ответ:

n^log(n!) 
(n+1)!  
n!
3^n
2^n
(3/2)^n
n^log(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!)=Θ(nlog(n))
n⋅ln(n)
nlog(2)=log(2^n )
(log(2))^n≈(0.3)^n
1/n=n^(-1)

Что вы думаете?

Answer 2

Вы хорошо сделали до сих пор.Поскольку это домашнее задание, я не буду давать точный ответ, а только намеки на те, которые вам не хватает:

• n^log(n): это растет быстрее, чем (log(n))^(log(n)), ноне так быстро, как экспоненты.Вы можете подтвердить это, сравнив log с этих трех выражений вместе.

• n*ln(n): ln(n) равно ln(10)log(n).В общем случае, log a в базе c, это log a в базе b, умноженной на log b в базе 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), которое медленно уменьшается на величину.