[理工]資節遞迴問題

[seika555 (kakkoii)]

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
推 henry78925: 你要計算time comp，其實你去想第一層就好 試想第一層
→ henry78925: 是拆成兩個一半的A丟進遞迴，2T(n/2) 接著判斷A[m]、A
→ henry78925: [j] θ(1)，最後遞迴(A,i,j-1)→T(n-1)。
→ henry78925: 標點符號打的有點爛，將就點謝謝
謝謝he大，第一層是指遞迴開始的第一round 嗎
因為常常看到題目就實際拿數字帶，想很久，所以是每題都可以這樣想嗎？
※ 編輯: seika555 (114.137.58.189), 08/11/2018 15:05:43
推 henry78925: 對的因為當你寫T(n)=aT(n/b) 的形式，遞迴的部分aT(n/
→ henry78925: b)這就會幫你遞迴下去了，所以只要第一層正確，就會是
→ henry78925: 對的。
我懂了 謝謝h大
※ 編輯: seika555 (114.137.185.127), 08/11/2018 17:57:36