推 gary19941208: 我也對recursive tree 陌生QQ 11/17 17:53
推 Transfat: 為什麼T(1)=M阿有點不懂 12/20 17:18
※ 引述《boy00114 (ponny)》之銘言：
: 哈囉大家早
: 我今天在寫成大與台大這兩題的時候，覺得是同樣的算法但是答案差了一個M倍，請大家幫忙解答><
: 成大103
: http://i.imgur.com/Ot1vh7I.jpg
: http://i.imgur.com/0lhSCBv.jpg
: 臺大105
: http://i.imgur.com/pVqbBW5.jpg
小弟對於 recuiuve tree 其實很陌生 , 通常都會用 substitution 去解
今天靈光乍現想到 substitution 的解法
手機請用整頁模式
T(n) = 8 T(n/2) + θ(1) , if n^2 > M
= M , if n^2 ≦ M
2
(ｎ) ｎ
n^2 > M => ─── > 1 => ─── > ±1
Ｍ √Ｍ
(1/2) (1/2)
=> n / M > 1 or n / M < -1
2
(ｎ)
n^2 ≦M => ─── ≦ 1
Ｍ
（ｎ）
=> ─── ≦ ±1
√M
(ｎ)
當 ─── > 1 , T(n) = 8 T(n/2) + θ(1)
√M
ｎ k
令 ─── = 2
√M
ｎ ｎ k k-1
T ( ─── ) = 8T(───) + θ(1) => T(2)= 8T(2) + θ(1)
√M √M/2
k
令 S(k) = T(2)
則 S(k) = 8 S(k-1) + θ(1)
= 8*8*S(k-2) + θ(8) + θ(1)
. k
. k ８－１
= 8 S(0) + θ(───)
８－１
k k 0 k
T(2) = 8 T(2)+ c * (8 / 7)
k k
= 8 * M + c * (8 / 7)
ｎ ｎ
lg (───) lg (───)
√M √M
= ８ * M + c * ８ ／７
８
ｎ 3 ｎ lg ─
= (───) * M + c(───) ７
√M √M
3 3
ｎ ｎ
= ─── = θ(───)
√M √M
--
有一個香錦囊，是從一個神話般的守軍的血屍頂上剝下的。那一次我們部隊遭受從未
有過的頑強抵抗，我們犧牲了三個艦隊，一個裝甲師和無以數計小組推進的敢死排，才摧
毀了那處隘口的碉堡。但是竟然發現，使我們遭受如此慘烈傷亡的守軍，總數只有一人。
士兵們起鬨地在他胸前發現這枚香袋，大家都相信這是一枚具有神奇力量的護身符。
我們把他的頭顱砍斷，取下香袋，剝開，
裡面一張被血浸紅的宣紙竟用漢字娟娟秀秀四個整齊的楷書寫著－「盼君早歸。」
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.27.202
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.A.90A.html
※ 編輯: ken52011219 (36.224.27.202), 11/17/2016 14:19:32