※ 引述《boy00114 (ponny)》之铭言：
: 哈囉大家早
: 我今天在写成大与台大这两题的时候，觉得是同样的算法但是答案差了一个M倍，请大家帮忙解答><
: 成大103
:

:

: 台大105
:

小弟对于 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

我也对recursive tree 陌生QQ