[理工]100.101資結 交大 程式碼推算複雜度問題

看板Grad-ProbAsk作者 (co)時間8年前 (2016/01/15 15:28), 8年前編輯推噓2(2推 0噓 8→)
留言10則, 4人參與, 最新討論串1/1
如題 100年交大第1題 http://imgur.com/GhKatDx
答案是B A 101年交大第12題之36小題 http://imgur.com/gZ4CnqW
答案是A 類似這種含有函式或者遞迴的時間複雜度 我每次都求錯= = 拜託大家指點了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.97.99 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452842924.A.BC9.html
→
01/15 16:48, , 1F
36 e?
01/15 16:48, 1F
是A喔 你也是用T(n)=2T(n/2)+1來算的嘛?? QQ ※ 編輯: iam30719 (1.160.97.99), 01/15/2016 17:37:22 ※ 編輯: iam30719 (1.160.97.99), 01/15/2016 17:39:03
推
01/15 17:50, , 2F
T(n)=2T(n/2)+kn. k為常數,再用master theorem 解
01/15 17:50, 2F
請問kn是怎樣看出來的?? 能說明一下嗎QQ
→
01/15 18:58, , 3F
第一題是heap的調整,cost等於父結點數
01/15 18:58, 3F
→
01/15 18:59, , 4F
一之2就像binary search
01/15 18:59, 4F
所以用trace的方式去求有辦法嗎 還是就是要大量的程式碼閱讀= = ※ 編輯: iam30719 (1.160.97.99), 01/15/2016 19:14:40 ※ 編輯: iam30719 (1.160.97.99), 01/15/2016 19:16:08
→
01/15 19:29, , 5F
沒到大量,把經典sort,search,各tree結構的code弄一弄
01/15 19:29, 5F
→
01/15 19:29, , 6F
吧，考手寫也是很可能的
01/15 19:29, 6F
→
01/15 19:30, , 7F
101那題最後有提到overhead
01/15 19:30, 7F
推
01/15 21:15, , 8F
each have an overhead of O(n)
01/15 21:15, 8F
※ 編輯: iam30719 (42.72.217.83), 01/17/2016 10:44:30
→
01/21 18:22, , 9F
講錯，第一題是max heap bottom-up建立，複雜度用數
01/21 18:22, 9F
→
01/21 18:22, , 10F
學推導
01/21 18:22, 10F
‣ 更多 iam30719 的文章
文章代碼(AID): #1Mc9-il9 (Grad-ProbAsk)