[理工]清大102計科

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間9年前 (2016/12/29 10:07), 編輯推噓3(3推 0噓 23→)
留言26則, 4人參與, 最新討論串2/2 (看更多)
請問b,c要怎麼寫? http://i.imgur.com/ZjcqNo6.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.235.130.102 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482977267.A.61F.html
推
12/29 11:42, , 1F
(b) f(n)=2f(n/2)+n, f(1)=0; (c) n*(2^n); 有錯請見
12/29 11:42, 1F
→
12/29 11:42, , 2F
諒
12/29 11:42, 2F
推
12/29 11:44, , 3F
(b)我搞不太清楚是要遞迴關係式還是他的時間複雜度
12/29 11:44, 3F
→
12/29 11:51, , 4F
b要求他的時間複雜度的遞迴式
12/29 11:51, 4F
→
12/29 11:55, , 5F
被切成一半有兩個 n/2 所以時間也要繼續再花2f(n/2)
12/29 11:55, 5F
→
12/29 11:55, , 6F
然後每跑一輪要c*n time吧 所以才有那個式子
12/29 11:55, 6F
→
12/29 11:59, , 7F
我寫的有點不一樣:http://i.imgur.com/WcO5I
12/29 11:59, 7F
→
12/29 12:01, , 8F
上傳完才發現，推導過程寫cn比n好
12/29 12:01, 8F
→
12/29 12:08, , 9F
T(1)不知道該訂為1還是0好？
12/29 12:08, 9F
推
12/29 14:12, , 10F
yupog2003大:我覺得這題應該是0比較好 因為他前面有if(
12/29 14:12, 10F
→
12/29 14:12, , 11F
n>1)
12/29 14:12, 11F
→
12/29 14:35, , 12F
嗯嗯，這樣講也對，我當初是想說if判斷也要花時間就設
12/29 14:35, 12F
→
12/29 14:35, , 13F
為1，也有可能是我想多了，如同只是問print的time comp
12/29 14:35, 13F
→
12/29 14:35, , 14F
lecity的確是0比較好
12/29 14:35, 14F
→
12/29 14:37, , 15F
果
12/29 14:37, 15F
→
12/29 19:37, , 16F
所以y大的答案是
12/29 19:37, 16F
→
12/29 19:37, , 17F
(b) T(n)=2T(n/2)+theta(n)
12/29 19:37, 17F
→
12/29 19:38, , 18F
(c) theta(nlogn)
12/29 19:38, 18F
→
12/29 19:38, , 19F
這樣嗎?
12/29 19:38, 19F
→
12/29 19:43, , 20F
我發現我的link有問題XD
12/29 19:43, 20F
→
12/29 19:43, , 21F
12/29 19:43, 21F
→
12/29 19:44, , 22F
其實就是那樣，只是(b)要記得加初始條件而已
12/29 19:44, 22F
→
12/29 19:50, , 23F
那T(1)要改成0嗎?
12/29 19:50, 23F
→
12/29 20:02, , 24F
這個就問倒我了，只問print的time complexity的話就一
12/29 20:02, 24F
→
12/29 20:02, , 25F
定是0，可是如果加上if判斷式就是1，只能寫答案的時候
12/29 20:02, 25F
→
12/29 20:03, , 26F
跟老師說清楚吧！
12/29 20:03, 26F
‣ 更多 h9638512 的文章
文章代碼(AID): #1OP6_pOV (Grad-ProbAsk)
‣ 更多 h9638512 的文章
文章代碼(AID): #1OP6_pOV (Grad-ProbAsk)