作者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/cn.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