[理工] 資料結構_p.36 試題6

看板Grad-ProbAsk作者 (fmtshk)時間5年前 (2019/06/02 21:13), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 5年前最新討論串1/1
https://i.imgur.com/MfrL0J3.jpg
https://i.imgur.com/SGrJV8U.jpg
請問第三小題這段英文題目是什麼意思呢？ "recursively processes two equal halves of a problem that each have an overhead of O(n)?" 查翻譯是“遞迴處理問題的兩個想等的一半？” 有點不太懂@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.13.98.107 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1559481204.A.EAF.html
推
06/02 21:37, 5年前 , 1F
每個問題遞迴處理變成兩個size為一半的子問題
06/02 21:37, 1F
→
06/02 21:59, 5年前 , 2F
那再問一下(3)的答案旁寫T(N)=2T(n/2)+theta(n)為何要多
06/02 21:59, 2F
→
06/02 21:59, 5年前 , 3F
個theta(n)呢？
06/02 21:59, 3F
推
06/02 22:12, 5年前 , 4F
最後說overhead是O(n)，所以每步驟有theta(n)的cost
06/02 22:12, 4F
→
06/03 16:32, 5年前 , 5F
看懂了，謝謝
06/03 16:32, 5F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1Syyjqwl (Grad-ProbAsk)