作者ouskit (ouskit)
看板Grad-ProbAsk
标题[理工] 资结 selection tree
时间Wed Jan 1 22:32:31 2020
http://i.imgur.com/EpYMCaR.jpg
http://i.imgur.com/V780JSj.jpg
请问这题中 per level 的时间为什麽是 O（nlog2(k)）?! 到底怎麽来的
-----
Sent from JPTT on my Samsung SM-G970F.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.16.216 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577889153.A.C1F.html
1F：推 mistel: 我的理解是这边的selection tree是用在每一层的k-way mer 01/01 22:59
2F：→ mistel: ge上 01/01 22:59
4F：→ mistel: 如图，在决策树每一层中的目标是合并k个run变成1个run， 01/01 23:05
5F：→ mistel: 利用selection tree，建tree时间可以不管。 01/01 23:05
6F：→ mistel: 1.每次从k个run中决定最小值相当於selection tree的树高 01/01 23:05
7F：→ mistel: 2.因为k-way，一共有k*(n/m)个data要爬上root 01/01 23:05
8F：→ mistel: 3.一共有m/k棵selection tree要做，所以把这些相乘就是O( 01/01 23:05
9F：→ mistel: nlog_2k) 01/01 23:05
10F：→ mistel: 第二步骤就是计算决策树的高度，这是总共merge的次数，算 01/01 23:06
11F：→ mistel: 出来就是答案了 有错还请指正>_< 01/01 23:06
非常清楚与明了！
谢谢m大 (/^▽^)/
※ 编辑: ouskit (220.135.16.216 台湾), 01/02/2020 00:16:30