作者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/m.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