作者jimmylin1024 (shibaLover)
看板Grad-ProbAsk
標題[理工] 105台大電機 非選4 參考答案
時間Sat Dec 12 11:38:21 2020
板上沒找到解答 就自己寫了一個 希望可以拋磚引玉 想問板上大神們有沒有想到時間複雜度更低的解法呢？
題目如下：
https://i.imgur.com/ncMbVkF.jpg
參考解答：
https://i.imgur.com/sHvMN1T.jpg
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.31.221 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1607744303.A.263.html
1F：推 CSGD: 如果用min heap, find-min可以降到O(1), build可以降到O(n) 12/12 12:48
2F：→ CSGD: 不過我是用nxn matrix, min另存, 這樣每次更新需檢查2n-1個e 12/12 12:51
3F：→ CSGD: ntry 12/12 12:51
4F：推 mathtsai: 1.建好n^2個f(x,y) -> O(n^2) 12/12 12:52
5F：→ mathtsai: 2.用這n^2個元素建立heap -> O(n^2) 12/12 12:52
6F：→ mathtsai: 3.m次操作 會更動m*(2n-1)個decrease-key -> O(mnlgn) 12/12 12:54
7F：→ CSGD: 我nxn沒有建heap, 只有存matrix, 每次改值只在更動到的(2n-1 12/12 13:06
8F：→ CSGD: )個entry找最小和目前的min比, 我自己推是O(mn), 還是哪裡想 12/12 13:06
9F：→ CSGD: 錯了呢QQ 12/12 13:06
10F：→ mathtsai: matrix一開始用完就丟進heap裡了 要改都在heap改 12/12 13:12
11F：→ CSGD: 所以我沒有要建heap...只是2d array 12/12 13:16
12F：→ mathtsai: C大 m次更動中有可能改到最小的元素 這樣要怎麼找min？ 12/12 13:35
13F：推 CSGD: 對...那應該還是要用n個heap才對，感謝! 12/12 13:51
14F：推 joywilliamjo: 我是寫建立min-heap欸，這樣找min都是O(1),n個就O(n 12/12 14:23
15F：→ joywilliamjo: ),insert/delete也是O(nlgn) 12/12 14:23
16F：推 asd3136396: 我的想法是先建出nxn的元素 12/12 14:41
17F：→ asd3136396: 然後放進Fibonacci heap O(n^2) 12/12 14:41
18F：→ asd3136396: 更改一次decrease-key O(2n-1) 12/12 14:41
19F：→ asd3136396: 共m次O(mn) 12/12 14:41
20F：→ asd3136396: total（n^2+mn) 12/12 14:41
21F：→ asd3136396: 這樣想不知道有沒有錯 12/12 14:41
22F：→ jimmylin1024: 感謝各位大大！ 12/12 15:02
23F：→ jimmylin1024: a大用Fibonacci Heap時間複雜度沒錯。 原本我卡的點 12/12 15:02
24F：→ jimmylin1024: 是在做decrease key之前要先search這個element ，會 12/12 15:02
25F：→ jimmylin1024: 是O(n)，所以才轉而可慮用AVL。 12/12 15:02
26F：→ jimmylin1024: 不過後來想到可以用hashmap 來記錄各個點的在heap 12/12 15:02
27F：→ jimmylin1024: 中index 位置，這樣Fibonacci 的decrease key就可以 12/12 15:02
28F：→ jimmylin1024: amortize O(1) 12/12 15:02
29F：→ jimmylin1024: 整體time complexity 就會是O(n^2) 12/12 15:02
30F：→ jimmylin1024: m更新的話就會是O(mn) 12/12 15:02
31F：→ mathtsai: 喔喔 Fibonacci heap時間當然快(？ 12/12 23:12