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