[其他] 關於時間複雜度（big O）的排序

[MMaze (Maze)]

大家好，想請教大家一題關於執行程式時，各函數的時間複雜度的排序。
題目將以下所有函數依照時間複雜度O排序，由大到小:

・N^2 + logN
・2^(2^N)
・NlogN
・lnN
・(n+1)!
・lg(lgN)
・n^3
・n!
・(3/2)^N
・2^(logN)

以下是我的排序，時間複雜度最大排到最小的

1. N! , (N+1)! ----這兩個相等 都是O(N)
2. 2^(2^N)     ----比O(C^N)又更大
3. (3/2)^N     ----O(C^N) (Exponential)
4. 2^(logN)    ----比O(C^N)小因為是指數是放logN
5. n^3         ----O(N^3)
6. N^2 + logN  ----O(N^2)
7. NlogN       ----O(NlogN)
8. lnN         ----O(logN)
9. lg(lgN)     ----O(loglogN)

想問大家以上的排序正不正確?

我最主要的疑惑是 2^(2^N) , (3/2)^N , 2^(logN) 這三個，
他們都是Exponential的成長速度，但因為指數部分又有包含N在內變數，
所以應該是要照我的排序，還是其實他們三個的時間複雜度都一樣呢?

謝謝!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 103.232.136.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1639204484.A.AC6.html
推 bigbigloser : 如果是以2為底，2^(log(N))就是N
→ bigbigloser : 然後2^(2^N)比N!大才對(一項一項比較)
→ MMaze       : to樓上，如果非２為底呢？　
→ MMaze       : 另外，為什麼2^(2^N)比N!大？階乘不是複雜度最高嗎?
推 tsoahans    : 兩邊取log比 log(N!)<NlogN<N^2<2^N=log(2^(2^N))
推 usir166     : 你每項後面用的是big o notation，可以去看一下定義
→ usir166     : big-o是函數漸進的上界，因此一個函數的big-O表達
→ usir166     : 並不唯一，而即使big-O一樣的不同函數時間複雜度也
→ usir166     : 不一定會一樣，而向一些常見的big-O notation分類如
→ usir166     : logn,n,n^2,2^n,n!等等，是因為常用，而不是一定只
→ usir166     : 能用這幾種分類
→ bigbigloser : a^(log(b))=b^(log(a))，2^(2^N)=2*2^(1+2+...+2^(N
→ bigbigloser : -1))