[理工] 96清大資結

[PTT007 (鍵盤007)]

http://0rz.tw/8ifl3

請問我框起來那裡，為什麼n要除以k

這題不是很懂，有人可以解釋嗎？ 感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.111.245
推 A4P8T6X9:因為leaf個數，每一個leaf大小k有n/k個，所以高度約等於
→ A4P8T6X9:log(n/k)
推 patabon:他的意思是說，原本merge sort會一直把n分割成n/2.n/2下去
→ patabon:遞迴，但這邊改成一直分割到每個run的元素個數小於k之後
→ patabon:就停止遞迴，然後改用insert sort做完之後再回傳給上面
→ patabon:做merge.
推 patabon:畫了一張很草的示意圖。http://ppt.cc/K2-v
→ PTT007:感謝~~~