[理工] 96清大資結

看板Grad-ProbAsk作者 (鍵盤007)時間10年前 (2014/01/05 00:02), 編輯推噓3(3推 0噓 5→)
留言8則, 3人參與, 最新討論串1/1
http://0rz.tw/8ifl3 請問我框起來那裡，為什麼n要除以k 這題不是很懂，有人可以解釋嗎？ 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.111.245
推
01/05 00:16, , 1F
因為leaf個數，每一個leaf大小k有n/k個，所以高度約等於
01/05 00:16, 1F
→
01/05 00:17, , 2F
log(n/k)
01/05 00:17, 2F
推
01/05 12:30, , 3F
他的意思是說，原本merge sort會一直把n分割成n/2.n/2下去
01/05 12:30, 3F
→
01/05 12:32, , 4F
遞迴，但這邊改成一直分割到每個run的元素個數小於k之後
01/05 12:32, 4F
→
01/05 12:33, , 5F
就停止遞迴，然後改用insert sort做完之後再回傳給上面
01/05 12:33, 5F
→
01/05 12:34, , 6F
做merge.
01/05 12:34, 6F
推
01/05 12:48, , 7F
畫了一張很草的示意圖。http://ppt.cc/K2-v
01/05 12:48, 7F
→
01/05 22:53, , 8F
感謝~~~
01/05 22:53, 8F
‣ 更多 PTT007 的文章
文章代碼(AID): #1Io32E8- (Grad-ProbAsk)