※ 引述《bernachom (Terry)》之銘言：
: 不好意思，請教一下
: 如果n=2^2^k
: T(n)=3T(√n)+logn
: 經過計算
: => 3^k F(0)+k2^k
: ^^^^^
: 不知道的地方是為什麼會有“K個“2^K...
: 那K個是從哪來的呢?
: //我把問題寫清楚一點
: 算到最後一般化時~
: 如果是F(K)就會是3^k F(0)+k2^k
: 如果是F(K-K)就會是3^K F(0)+3^K-1*2^1+3^K-2*2^2+...+3^0*2^K
: 是這樣子嗎???
: 謝謝幫忙
我來補充一下我之前的推文好了
令m=logn 所以n=10^m, n^(1/2)=10^(m/2)
原式變成T(10^m) = 3T(10^(m/2)) + m
再令S(m) = T(10^m)
S(m) = 3S(m/2) + m
change variable的目的是為了讓遞迴式能用master解
所以這邊是case 1
O(m^lg3) = O(logn^lg3) = O(3^lglogn)
感覺有點怪怪的 不知道有沒有地方是錯的= =
請版上高手指正一下...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: mqazz1 來自: 140.118.33.178 (11/18 12:43)