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

看板Grad-ProbAsk作者 (Broken Coastline)時間5年前 (2020/07/03 09:44), 5年前編輯推噓2(2推 0噓 7→)
留言9則, 2人參與, 5年前最新討論串1/1
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
推
07/03 09:59, 5年前 , 1F
本來就是看個數來merge啊
07/03 09:59, 1F
推
07/03 09:59, 5年前 , 2F
不論從哪一對list, L_i & L_j(i, j belong to m)開始
07/03 09:59, 2F
→
07/03 09:59, 5年前 , 3F
merge，一共merge (m-1)次，最後都會merge成一個List
07/03 09:59, 3F
→
07/03 09:59, 5年前 , 4F
，這樣設計的用意在於minimize每一次Linear merge，你
07/03 09:59, 4F
→
07/03 09:59, 5年前 , 5F
可以想像一開始從最大的List(some n_i is maximal )開
07/03 09:59, 5F
→
07/03 09:59, 5年前 , 6F
始merge，這樣每次Linear merge就是從n_i開始加，至少
07/03 09:59, 6F
→
07/03 09:59, 5年前 , 7F
有(m-1)*n_i個operations
07/03 09:59, 7F
懂了，謝謝！！
→
07/03 10:00, 5年前 , 8F
每次都選一樣個數的merge 才可以到O(nlgn)
07/03 10:00, 8F
感謝c大解釋，這樣有點懂了
→
07/03 10:02, 5年前 , 9F
有點像Huffman tree的概念
07/03 10:02, 9F
※ 編輯: ff00662299 (117.19.148.169 臺灣), 07/03/2020 16:55:23 ※ 編輯: ff00662299 (117.19.148.169 臺灣), 07/03/2020 16:56:09
‣ 更多 ff00662299 的文章
文章代碼(AID): #1U_ercdy (Grad-ProbAsk)