作者frank73 (sigh)
站內Grad-ProbAsk
標題[理工] 計概
時間Wed Feb 8 22:36:34 2012
1. 找upper bound跟lower bound
T(n) = 2T(n/2) + n/log(n)
=> 這題好像沒辦法用master theorem
我有嘗試展開
T(n) = 2^log(n) + n/log(n) + n/log(n/2) + n/log(n/4) + ...
> 2^log(n) + n/log(n) + n/log(n) + n/log(n) + ...
= n + n/log(n)*log(n)
= 2n
Ω(T(n)) = n
T(n) = 2^log(n) + n/log(n) + n/log(n/2) + n/log(n/4) + ...
< 2^log(n) + n/log(n/(2)^log(n)) + n/log(n/(2)^log(n)) + ...
= n + n/log(n/(2)^log(n))*log(n)
= n
O(T(n)) = n
不知道我這樣寫對不對!?
2. please find the values in the list below that produce the sum 2200
191 691 573 337 365 730 651 493 177 354
=> 這題完全沒想法, 除了暴力法, 有其他方法嘛@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.192.250
推 iamjustakid:第一題是nloglogn喔 02/08 22:54
→ rayway30419:第二題是要DP嗎 02/08 22:55
→ frank73:可以請問怎麼算出來的嘛@@ 02/08 22:56
推 iamjustakid:我是令n=2^K 帶入算 02/08 23:03
→ iamjustakid:另外Recursion tree也可以解 02/08 23:04
推 rayway30419:let n=2^k 直接代入就可以摟~ 02/08 23:05
→ frank73:感謝樓上兩位:) 02/08 23:21
推 rayway30419:有人會第二題嗎?@"@ 02/08 23:26
推 bbhands:2. 691+365+651+493 我是mod 11以後湊一下 02/08 23:34
推 zensword:大家第一題的n=2^k 怎麼代的？ 是用到調和數列=logn? 02/09 00:04
推 rayway30419:直接代進去就可以解了 補習班解法通常會把遞迴弄清楚 02/09 00:07
→ suhorng:harmonic series + 1 02/09 08:42