[理工] 算法 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