為什麼這篇Big O 定義鄉民發文收入到精華區：因為在Big O 定義這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者MMaze (Maze)看板Math標題[其他] 關於時間複雜度（big O）的排序時間Sat ...
Big O 定義 在 ♡ ????????.? 張惟婷 Instagram 的最佳貼文
2021-08-02 18:42:56
#造型師們都不約而同遞給我粉色上衣穿的部分 感謝我的直播平台Bigo給我這次機會耍美 確定的是台灣220台台灣大車隊計程車外面會有我出現了👏 220個惟婷在馬路上奔跑有沒有很酷 歡迎追焦🚕 「趁機打廣告📣BIGO徵主播」 這次拍攝終於有點瘦感了 總覺得棚拍到最後都會回到我最自然的樣子 (精神分裂的部...
大家好，想請教大家一題關於執行程式時，各函數的時間複雜度的排序。
題目將以下所有函數依照時間複雜度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 12/11 15:43
→ bigbigloser : 然後2^(2^N)比N!大才對(一項一項比較) 12/11 15:46
→ MMaze : to樓上，如果非２為底呢？ 12/11 16:12
→ MMaze : 另外，為什麼2^(2^N)比N!大？階乘不是複雜度最高嗎? 12/11 16:12
推 tsoahans : 兩邊取log比 log(N!)<NlogN<N^2<2^N=log(2^(2^N)) 12/11 18:06
推 usir166 : 你每項後面用的是big o notation，可以去看一下定義 12/11 20:35
→ usir166 : big-o是函數漸進的上界，因此一個函數的big-O表達 12/11 20:37
→ usir166 : 並不唯一，而即使big-O一樣的不同函數時間複雜度也 12/11 20:39
→ usir166 : 不一定會一樣，而向一些常見的big-O notation分類如 12/11 20:40
→ usir166 : logn,n,n^2,2^n,n!等等，是因為常用，而不是一定只 12/11 20:41
→ usir166 : 能用這幾種分類 12/11 20:43
→ bigbigloser : a^(log(b))=b^(log(a))，2^(2^N)=2*2^(1+2+...+2^(N 12/11 22:03
→ bigbigloser : -1)) 12/11 22:04