[理工] 105台大電機 非選4 參考答案

看板Grad-ProbAsk作者 (shibaLover)時間5年前 (2020/12/12 11:38), 編輯推噓5(5推 0噓 26→)
留言31則, 5人參與, 5年前最新討論串1/1
板上沒找到解答 就自己寫了一個 希望可以拋磚引玉 想問板上大神們有沒有想到時間複雜度更低的解法呢？ 題目如下： 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1607744303.A.263.html
推
12/12 12:48, 5年前 , 1F
如果用min heap, find-min可以降到O(1), build可以降到O(n)
12/12 12:48, 1F
→
12/12 12:51, 5年前 , 2F
不過我是用nxn matrix, min另存, 這樣每次更新需檢查2n-1個e
12/12 12:51, 2F
→
12/12 12:51, 5年前 , 3F
ntry
12/12 12:51, 3F
推
12/12 12:52, 5年前 , 4F
1.建好n^2個f(x,y) -> O(n^2)
12/12 12:52, 4F
→
12/12 12:52, 5年前 , 5F
2.用這n^2個元素建立heap -> O(n^2)
12/12 12:52, 5F
→
12/12 12:54, 5年前 , 6F
3.m次操作 會更動m*(2n-1)個decrease-key -> O(mnlgn)
12/12 12:54, 6F
→
12/12 13:06, 5年前 , 7F
我nxn沒有建heap, 只有存matrix, 每次改值只在更動到的(2n-1
12/12 13:06, 7F
→
12/12 13:06, 5年前 , 8F
)個entry找最小和目前的min比, 我自己推是O(mn), 還是哪裡想
12/12 13:06, 8F
→
12/12 13:06, 5年前 , 9F
錯了呢QQ
12/12 13:06, 9F
→
12/12 13:12, 5年前 , 10F
matrix一開始用完就丟進heap裡了 要改都在heap改
12/12 13:12, 10F
→
12/12 13:16, 5年前 , 11F
所以我沒有要建heap...只是2d array
12/12 13:16, 11F
→
12/12 13:35, 5年前 , 12F
C大 m次更動中有可能改到最小的元素 這樣要怎麼找min？
12/12 13:35, 12F
推
12/12 13:51, 5年前 , 13F
對...那應該還是要用n個heap才對，感謝!
12/12 13:51, 13F
推
12/12 14:23, 5年前 , 14F
我是寫建立min-heap欸，這樣找min都是O(1),n個就O(n
12/12 14:23, 14F
→
12/12 14:23, 5年前 , 15F
),insert/delete也是O(nlgn)
12/12 14:23, 15F
推
12/12 14:41, 5年前 , 16F
我的想法是先建出nxn的元素
12/12 14:41, 16F
→
12/12 14:41, 5年前 , 17F
然後放進Fibonacci heap O(n^2)
12/12 14:41, 17F
→
12/12 14:41, 5年前 , 18F
更改一次decrease-key O(2n-1)
12/12 14:41, 18F
→
12/12 14:41, 5年前 , 19F
共m次O(mn)
12/12 14:41, 19F
→
12/12 14:41, 5年前 , 20F
total（n^2+mn)
12/12 14:41, 20F
→
12/12 14:41, 5年前 , 21F
這樣想不知道有沒有錯
12/12 14:41, 21F
→
12/12 15:02, 5年前 , 22F
感謝各位大大！
12/12 15:02, 22F
→
12/12 15:02, 5年前 , 23F
a大用Fibonacci Heap時間複雜度沒錯。 原本我卡的點
12/12 15:02, 23F
→
12/12 15:02, 5年前 , 24F
是在做decrease key之前要先search這個element ，會
12/12 15:02, 24F
→
12/12 15:02, 5年前 , 25F
是O(n)，所以才轉而可慮用AVL。
12/12 15:02, 25F
→
12/12 15:02, 5年前 , 26F
不過後來想到可以用hashmap 來記錄各個點的在heap
12/12 15:02, 26F
→
12/12 15:02, 5年前 , 27F
中index 位置，這樣Fibonacci 的decrease key就可以
12/12 15:02, 27F
→
12/12 15:02, 5年前 , 28F
amortize O(1)
12/12 15:02, 28F
→
12/12 15:02, 5年前 , 29F
整體time complexity 就會是O(n^2)
12/12 15:02, 29F
→
12/12 15:02, 5年前 , 30F
m更新的話就會是O(mn)
12/12 15:02, 30F
→
12/12 23:12, 5年前 , 31F
喔喔 Fibonacci heap時間當然快(？
12/12 23:12, 31F
‣ 更多 jimmylin1024 的文章
文章代碼(AID): #1Vr3il9Z (Grad-ProbAsk)