作者MMaze (Maze)
看板Math
標題[其他] 關於時間複雜度（big O）的排序
時間Sat Dec 11 14:34:42 2021
大家好，想請教大家一題關於執行程式時，各函數的時間複雜度的排序。
題目將以下所有函數依照時間複雜度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://webptt.com/m.aspx?n=bbs/Math/M.1639204484.A.AC6.html
1F：推 bigbigloser : 如果是以2為底，2^(log(N))就是N 12/11 15:43
2F：→ bigbigloser : 然後2^(2^N)比N!大才對(一項一項比較) 12/11 15:46
3F：→ MMaze : to樓上，如果非２為底呢？ 12/11 16:12
4F：→ MMaze : 另外，為什麼2^(2^N)比N!大？階乘不是複雜度最高嗎? 12/11 16:12
5F：推 tsoahans : 兩邊取log比 log(N!)<NlogN<N^2<2^N=log(2^(2^N)) 12/11 18:06
6F：推 usir166 : 你每項後面用的是big o notation，可以去看一下定義 12/11 20:35
7F：→ usir166 : big-o是函數漸進的上界，因此一個函數的big-O表達 12/11 20:37
8F：→ usir166 : 並不唯一，而即使big-O一樣的不同函數時間複雜度也 12/11 20:39
9F：→ usir166 : 不一定會一樣，而向一些常見的big-O notation分類如 12/11 20:40
10F：→ usir166 : logn,n,n^2,2^n,n!等等，是因為常用，而不是一定只 12/11 20:41
11F：→ usir166 : 能用這幾種分類 12/11 20:43
12F：→ bigbigloser : a^(log(b))=b^(log(a))，2^(2^N)=2*2^(1+2+...+2^(N 12/11 22:03
13F：→ bigbigloser : -1)) 12/11 22:04