PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 资结 selection tree
楼主:
ouskit
(ouskit)
2020-01-01 22:32:31
http://i.imgur.com/EpYMCaR.jpg
http://i.imgur.com/V780JSj.jpg
请问这题中 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的次数,算出来就是答案了 有错还请指正>_<
继续阅读
[理工] 资工 中央107 计系
zaqxsw2230
[理工] OS_SJF时间预估
fmtshk
[理工] 线代 SVD奇异值分解
yahooyamgoog
[理工] OS_demand paging
fmtshk
[理工] 108交大计系 fork
Lambo1228
[理工] 94清大 计组
marvelousbas
[理工] 成大103电通资结
beatssola
[理工] 交大103 计系
achicn3
[理工] 离散 1-72范例2
jean20157
[商管] 中央工工 一题机率
s035280236
Links
booklink
Contact Us: admin [ a t ] ucptt.com