作者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