[理工] 资结 selection tree
楼主: ouskit (ouskit) 2020-01-01 22:32:31
请问这题中 per level 的时间为什么是 O（nlog2(k)）?! 到底怎么来的
作者: mistel (Mistel) 2020-01-01 22:59:00
我的理解是这边的selection tree是用在每一层的k-way merge上https://i.imgur.com/JgKv6TB.jpg如图，在决策树每一层中的目标是合并k个run变成1个run，利用selection tree，建tree时间可以不管。1.每次从k个run中决定最小值相当于selection tree的树高2.因为k-way，一共有k*(n/m)个data要爬上root3.一共有m/k棵selection tree要做，所以把这些相乘就是O(nlog_2k)第二步骤就是计算决策树的高度，这是总共merge的次数，算出来就是答案了 有错还请指正>_<