[理工] 資結 selection tree
作者: ouskit (ouskit) 2020-01-01 22:32:31
請問這題中 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的次數，算出來就是答案了 有錯還請指正>_<