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