[理工] 演算法 3-37 D.P. 2-way merge tree ff00662299 PTT批踢踢實業坊

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

作者: ff00662299 (goneboy) 2020-07-03 09:44:04

https://i.imgur.com/71xY4Ws.jpg
https://i.imgur.com/dIHxuHI.jpg
不懂解答的key值，
是指list元素個數，
為什麼會以元素個數來做merge的依據？
不是用run中最小值去合併嗎？

作者: cossetannie (paa) 2020-07-03 09:59:00

本來就是看個數來merge啊

作者: b10007034 (Warren) 2020-07-03 09:59:00

不論從哪一對list, L_i & L_j(i, j belong to m)開始merge，一共merge (m-1)次，最後都會merge成一個List，這樣設計的用意在於minimize每一次Linear merge，你可以想像一開始從最大的List(some n_i is maximal )開始merge，這樣每次Linear merge就是從n_i開始加，至少有(m-1)*n_i個operations

作者: cossetannie (paa) 2020-07-03 10:00:00

每次都選一樣個數的merge 才可以到O(nlgn)有點像Huffman tree的概念

繼續閱讀

[理工] 線代 5-113 範例57s3251994 [理工] 線代1-25NTUmaki [理工] 線代第二章範例11ap15021 [理工] 演算法時間複雜度講義p21siuoly [理工] 線性代數黃子嘉上冊第三章證明a123543 [理工] 101台大資結lucy35 [理工] 離散 8-4傳輸傳輸網路ff00662299 [理工] 布林代數簡化gowrite Re: [理工]集合論GodlikePeter [理工] OS deadlockyoz4ni