[理工]資節遞迴問題

看板Grad-ProbAsk作者 (kakkoii)時間7年前 (2018/08/11 00:30), 7年前編輯推噓2(2推 0噓 5→)
留言7則, 1人參與, 7年前最新討論串1/1
https://imgur.com/p5WIr96.jpg
上圖題目第一小題的divide and conquer 的觀念我還可以理解 但第二小題寫成遞迴式我就不太懂了 我知道有2*T(n/2)但是後面的加T(n-1) + θ(1) 是怎麼來的壓 還請大大們幫忙解惑 謝謝 -- -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.213.244 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1533918628.A.35D.html
推
08/11 01:23, 7年前 , 1F
你要計算time comp，其實你去想第一層就好 試想第一層
08/11 01:23, 1F
→
08/11 01:23, 7年前 , 2F
是拆成兩個一半的A丟進遞迴，2T(n/2) 接著判斷A[m]、A
08/11 01:23, 2F
→
08/11 01:23, 7年前 , 3F
[j] θ(1)，最後遞迴(A,i,j-1)→T(n-1)。
08/11 01:23, 3F
→
08/11 01:24, 7年前 , 4F
標點符號打的有點爛，將就點謝謝
08/11 01:24, 4F
謝謝he大，第一層是指遞迴開始的第一round 嗎 因為常常看到題目就實際拿數字帶，想很久，所以是每題都可以這樣想嗎？ ※ 編輯: seika555 (114.137.58.189), 08/11/2018 15:05:43
推
08/11 16:50, 7年前 , 5F
對的因為當你寫T(n)=aT(n/b) 的形式，遞迴的部分aT(n/
08/11 16:50, 5F
→
08/11 16:50, 7年前 , 6F
b)這就會幫你遞迴下去了，所以只要第一層正確，就會是
08/11 16:50, 6F
→
08/11 16:50, 7年前 , 7F
對的。
08/11 16:50, 7F
我懂了 謝謝h大 ※ 編輯: seika555 (114.137.185.127), 08/11/2018 17:57:36
‣ 更多 seika555 的文章
文章代碼(AID): #1RRRsaDT (Grad-ProbAsk)