[理工] 資結 selection tree

看板Grad-ProbAsk作者 (ouskit)時間6年前 (2020/01/01 22:32), 6年前編輯推噓2(2推 0噓 9→)
留言11則, 1人參與, 6年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1577889153.A.C1F.html
推
01/01 22:59, 6年前 , 1F
我的理解是這邊的selection tree是用在每一層的k-way mer
01/01 22:59, 1F
→
01/01 22:59, 6年前 , 2F
ge上
01/01 22:59, 2F
推
01/01 23:00, 6年前 , 3F
01/01 23:00, 3F
→
01/01 23:05, 6年前 , 4F
如圖，在決策樹每一層中的目標是合併k個run變成1個run，
01/01 23:05, 4F
→
01/01 23:05, 6年前 , 5F
利用selection tree，建tree時間可以不管。
01/01 23:05, 5F
→
01/01 23:05, 6年前 , 6F
1.每次從k個run中決定最小值相當於selection tree的樹高
01/01 23:05, 6F
→
01/01 23:05, 6年前 , 7F
2.因為k-way，一共有k*(n/m)個data要爬上root
01/01 23:05, 7F
→
01/01 23:05, 6年前 , 8F
3.一共有m/k棵selection tree要做，所以把這些相乘就是O(
01/01 23:05, 8F
→
01/01 23:05, 6年前 , 9F
nlog_2k)
01/01 23:05, 9F
→
01/01 23:06, 6年前 , 10F
第二步驟就是計算決策樹的高度，這是總共merge的次數，算
01/01 23:06, 10F
→
01/01 23:06, 6年前 , 11F
出來就是答案了 有錯還請指正>_<
01/01 23:06, 11F
非常清楚與明瞭！ 謝謝m大 (/^▽^)/ ※ 編輯: ouskit (220.135.16.216 臺灣), 01/02/2020 00:16:30
‣ 更多 ouskit 的文章
文章代碼(AID): #1U3As1mV (Grad-ProbAsk)