作者ff00662299 (Broken Coastline)
看板Grad-ProbAsk
标题[理工] 演算法 3-37 D.P. 2-way merge tree
时间Fri Jul 3 09:44:04 2020
https://i.imgur.com/71xY4Ws.jpg
https://i.imgur.com/dIHxuHI.jpg
不懂解答的key值，
是指list元素个数，
为什麽会以元素个数来做merge的依据？
不是用run中最小值去合并吗？
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 117.19.148.169 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1593740646.A.9FC.html
1F：推 cossetannie: 本来就是看个数来merge啊 07/03 09:59
2F：推 b10007034: 不论从哪一对list, L_i & L_j(i, j belong to m)开始 07/03 09:59
3F：→ b10007034: merge，一共merge (m-1)次，最後都会merge成一个List 07/03 09:59
4F：→ b10007034: ，这样设计的用意在於minimize每一次Linear merge，你 07/03 09:59
5F：→ b10007034: 可以想像一开始从最大的List(some n_i is maximal )开 07/03 09:59
6F：→ b10007034: 始merge，这样每次Linear merge就是从n_i开始加，至少 07/03 09:59
7F：→ b10007034: 有(m-1)*n_i个operations 07/03 09:59
懂了，谢谢！！
8F：→ cossetannie: 每次都选一样个数的merge 才可以到O(nlgn) 07/03 10:00
感谢c大解释，这样有点懂了
9F：→ cossetannie: 有点像Huffman tree的概念 07/03 10:02
※ 编辑: ff00662299 (117.19.148.169 台湾), 07/03/2020 16:55:23
※ 编辑: ff00662299 (117.19.148.169 台湾), 07/03/2020 16:56:09