※ 引述《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