[理工] 102 成大 演算法

[Astar5566 (一顆星5566)]

(1)
FFTTF

(logn)!是指數
(lglgn)!也是指數

感謝板友指教！

(2)
1, T(n)=nlglgn
2, M個子問題 每次有d個選擇
3,
array : O(V*V)
binary heap : O(VlgV+ElgV)
f heap : O(VlgV+E)


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.50.71
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483969616.A.406.html
※ 編輯: Astar5566 (42.73.50.71), 01/09/2017 21:53:49
→ a15151616: 我是非題全部寫false
→ a15151616: 2.1 2.2答案應該是正確的
→ a15151616: 是非題第四題是true
→ yupog2003: 我是非跟你一樣FTTTF
→ yupog2003: 第二大題應該也是全對，不過第三小題我是有分Extract
→ yupog2003: min和Decrease分別做討論
→ Astar5566: 剛發現是非第二題的階乘是在外面 所以是F
※ 編輯: Astar5566 (42.73.50.71), 01/09/2017 22:37:40
→ a15151616: 是非第三題不用考慮forward path嗎
→ a15151616: 我剛剛翻到你最後三題答案跟立宇老師給的一樣
※ 編輯: Astar5566 (42.73.50.71), 01/09/2017 22:56:08
→ Astar5566: 感謝！ 我再去搞清楚dfs
→ a15151616: 是非題答案我翻了講義看到的應該是FFTTF
→ Astar5566: 有向圖才會有forward edge 可是也不會形成cycle 無向
→ Astar5566: 圖不會有forward edge都是back edge
→ Astar5566: 第三題應該是這樣 那第四題(lglgn)!不是指數嗎？
→ a15151616: 好的謝謝
※ 編輯: Astar5566 (42.73.50.71), 01/09/2017 23:08:41
→ a15151616: http://i.imgur.com/ZnbVMmN.jpg
推 joeboy: 如果n=2^n^n，那麼(lglgn)!還會是多項式嗎
→ Astar5566: http://i.imgur.com/3ahxgeT.jpg
→ Astar5566: (logn)!是指數 （loglogn)!是多項式
→ a15151616: j男孩n不能這樣看 你把你說的值化簡就變成(nlgn)!了