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

看板Grad-ProbAsk作者 (fmtshk)時間5年前 (2019/06/02 21:13), 編輯推噓2(203)
留言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
文章代碼(AID): #1Syyjqwl (Grad-ProbAsk)