[理工] 資料結構_p.36 試題6 fmtshk PTT批踢踢實業坊

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

作者: fmtshk (fmtshk) 2019-06-02 21:13:22

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)?"
查翻譯是“遞迴處理問題的兩個想等的一半？”
有點不太懂@@

作者: skyHuan (Huan) 2019-06-02 21:37:00

每個問題遞迴處理變成兩個size為一半的子問題

作者: fmtshk (fmtshk) 2019-06-02 21:59:00

那再問一下(3)的答案旁寫T(N)=2T(n/2)+theta(n)為何要多個theta(n)呢？

作者: skyHuan (Huan) 2019-06-02 22:12:00

最後說overhead是O(n)，所以每步驟有theta(n)的cost

作者: fmtshk (fmtshk) 2019-06-03 16:32:00

看懂了，謝謝

繼續閱讀

離散重複取組合應用問題zxc2179vbnm [理工] 電力系統問題olikatw 離散 p.3-17 範例三zxc2179vbnm [理工]資料結構p.1-34,複雜度計算fmtshk [理工] 請教一題電磁學考古題nick65415 離散第二章 104題zxc2179vbnm [理工] 離散環 9-101一題請益mistel [理工] 資料結構 heaptriumphant10 [理工] 線代—特徵值transform157 [理工] 離散樹的基本定義與性質sososlee