[理工] 演算法 3-37 D.P. 2-way merge tree

[ff00662299 (Broken Coastline)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1593740646.A.9FC.html
推 cossetannie: 本來就是看個數來merge啊
推 b10007034: 不論從哪一對list, L_i & L_j(i, j belong to m)開始
→ b10007034: merge，一共merge (m-1)次，最後都會merge成一個List
→ b10007034: ，這樣設計的用意在於minimize每一次Linear merge，你
→ b10007034: 可以想像一開始從最大的List(some n_i is maximal )開
→ b10007034: 始merge，這樣每次Linear merge就是從n_i開始加，至少
→ b10007034: 有(m-1)*n_i個operations
懂了，謝謝！！
→ cossetannie: 每次都選一樣個數的merge 才可以到O(nlgn)
感謝c大解釋，這樣有點懂了
→ cossetannie: 有點像Huffman tree的概念
※ 編輯: ff00662299 (117.19.148.169 臺灣), 07/03/2020 16:55:23
※ 編輯: ff00662299 (117.19.148.169 臺灣), 07/03/2020 16:56:09