來點補充說明, 因為 step 2 (refine) 不是一個很明顯的動作 (在這幾個 case 裡)
※ 引述《sandwichC (沒回應=掛站)》之銘言：
: 投影片中的例子
: S 10 7 2 4 12 6
: ----------------------------------------------------------
: R.M. 10 7 6 12 6 (2,4各加一次)
: refine 10 7 6 12 6
2+4 是 RM, 因為 2+4 <= 12, 所以 (2+4) 要被 "移" 到 12 前
order 剛好沒變.
: ----------------------------------------------------------
: R.M. 10 7 6 18 (12,6各加一次)
: refine 10 7 6 18
同上
: ----------------------------------------------------------
: R.M. 10 13 18 (7,2,4各加一次)
: refine 10 13 18
同上
: ----------------------------------------------------------
: R.M. 23 18 (10,7,2,4各加一次)
: refine 18 23
注意囉, 這裡不一樣!
10+13 之後, 沒有任何一個 single entry 大於或等於 23, 所以 23 移到最後.
: ----------------------------------------------------------
: R.M. 41 (10,7,2,4,12,6各加一次)
: total: 10加了兩次 (level = 2)
: 7加了三次 (level = 3)
: 2加了四次 (level = 4)
: 4加了四次 (level = 4)
: 12加了兩次 (level = 2)
: 6加了兩次 (level = 2)
: 故建出的tree：
: |
: -----------------
: | |
: | -------------
: | | |
: | | -----------
: | | | |
: ------- | | --------
: | | | | | |
: 12 6 10 7 2 4
^^^^^^^^^
注意到了嗎? 12 6 本來是在 4 之後, 現在跑到最前面來了.
有一件事投影片沒講清楚:
"把上面那顆樹變成另一顆樹, 其中各 leaf 的 depth 與在原樹中相同,
但 leaves 的順序與原數列一樣."
至於怎麼變, 這樣為什麼會找到最佳解, 就看看之前給的 link 吧
(其實我沒真的 go through 過, 但這比 windows2k 兄給的 slides 完整些 :P)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.137.27.253
※ 編輯: march20 來自: 71.137.27.253 (07/18 15:00)
※ 編輯: march20 來自: 71.137.27.253 (07/18 15:01)
※ 編輯: march20 來自: 71.137.27.253 (07/18 15:02)
※ 編輯: march20 來自: 71.137.27.253 (07/18 15:02)
※ 編輯: march20 來自: 71.137.27.253 (07/18 15:03)