作者lovefo (lovefo)
看板Grad-ProbAsk
標題Re: [理工] [資結]-成大97-資工 程式設計
時間Sat Feb 6 13:31:42 2010
※ 引述《IDontBite (IDontBite)》之銘言：
: ※ 引述《shinhwabo (.....)》之銘言：
: Solving the recurrence T(n)=2T(└√n┘)+㏒n using big-O notation as
: tight as possible
: 求板上的高手幫忙解答 thx
: Assume T(1) = O(1)
: T(n) = 2T(n^1/2) + logn
: = 2{2T(n^1/4) + log(n^1/2)} + logn
: = 4T(n^1/4) + 2*(1/2)logn + logn
: = 4T(n^1/4) + 2logn
: = (2^k)T(n^(1/2^k)) + klogn ----(a)
: T(2) = 2T(1) + logn = O(logn)
: 則令 n^(1/2^k) = 2 得 k = (logn)/2 代入(a)
: T(n) = n^(1/2)*T(2) + 1/2(logn)(logn)
: = O(√nlogn)
借題問一下
洪逸 分類題庫有寫這一題
在n很大時 原式約等於T(n)=2T(√n)+㏒n
令 n=2^2^k ,F(k)=T(2^2^k)
F(k)= 2F(k-1) + 2^k
= 2^2 F(k-2) + 2^k + 2^k
.
.
.
.
= 2^k F(k-k) + 2^k + 2^k + ......+2^k
= 2^k F(0) + k2^k
k=loglog n
T(n)=O(loglogn *log n)
這樣寫會不會零分阿
還是要照上面大大寫的會比較好??
--
一切....
似乎不再那麼重要....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.46.165.55
1F：→ taitin:為什麼會0分 02/06 17:38