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

看板Math作者 (Maze)時間2年前 (2021/12/11 14:34), 編輯推噓3(3推 0噓 10→)
留言13則, 4人參與, 2年前最新討論串1/2 (看更多)
大家好，想請教大家一題關於執行程式時，各函數的時間複雜度的排序。 題目將以下所有函數依照時間複雜度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
推
12/11 15:43, 2年前 , 1F
如果是以2為底，2^(log(N))就是N
12/11 15:43, 1F
→
12/11 15:46, 2年前 , 2F
然後2^(2^N)比N!大才對(一項一項比較)
12/11 15:46, 2F
→
12/11 16:12, 2年前 , 3F
to樓上，如果非２為底呢？　
12/11 16:12, 3F
→
12/11 16:12, 2年前 , 4F
另外，為什麼2^(2^N)比N!大？階乘不是複雜度最高嗎?
12/11 16:12, 4F
推
12/11 18:06, 2年前 , 5F
兩邊取log比 log(N!)<NlogN<N^2<2^N=log(2^(2^N))
12/11 18:06, 5F
推
12/11 20:35, 2年前 , 6F
你每項後面用的是big o notation，可以去看一下定義
12/11 20:35, 6F
→
12/11 20:37, 2年前 , 7F
big-o是函數漸進的上界，因此一個函數的big-O表達
12/11 20:37, 7F
→
12/11 20:39, 2年前 , 8F
並不唯一，而即使big-O一樣的不同函數時間複雜度也
12/11 20:39, 8F
→
12/11 20:40, 2年前 , 9F
不一定會一樣，而向一些常見的big-O notation分類如
12/11 20:40, 9F
→
12/11 20:41, 2年前 , 10F
logn,n,n^2,2^n,n!等等，是因為常用，而不是一定只
12/11 20:41, 10F
→
12/11 20:43, 2年前 , 11F
能用這幾種分類
12/11 20:43, 11F
→
12/11 22:03, 2年前 , 12F
a^(log(b))=b^(log(a))，2^(2^N)=2*2^(1+2+...+2^(N
12/11 22:03, 12F
→
12/11 22:04, 2年前 , 13F
-1))
12/11 22:04, 13F
‣ 更多 MMaze 的文章
文章代碼(AID): #1Xj4Q4h6 (Math)
‣ 更多 MMaze 的文章
文章代碼(AID): #1Xj4Q4h6 (Math)