推 mistel: 我的理解是這邊的selection tree是用在每一層的k-way mer 01/01 22:59
→ mistel: ge上 01/01 22:59
→ mistel: 如圖，在決策樹每一層中的目標是合併k個run變成1個run， 01/01 23:05
→ mistel: 利用selection tree，建tree時間可以不管。 01/01 23:05
→ mistel: 1.每次從k個run中決定最小值相當於selection tree的樹高 01/01 23:05
→ mistel: 2.因為k-way，一共有k*(n/m)個data要爬上root 01/01 23:05
→ mistel: 3.一共有m/k棵selection tree要做，所以把這些相乘就是O( 01/01 23:05
→ mistel: nlog_2k) 01/01 23:05
→ mistel: 第二步驟就是計算決策樹的高度，這是總共merge的次數，算 01/01 23:06
→ mistel: 出來就是答案了 有錯還請指正>_< 01/01 23:06
非常清楚與明瞭！
謝謝m大 (/^▽^)/
※ 編輯: ouskit (220.135.16.216 臺灣), 01/02/2020 00:16:30