Research Space for Linear Algebra & Discrete Mathematics
2*rec(n/2)+2*rec(n/2) = 2*(2*rec(n/2)) = 4*rec(n/2), 所以那兩個是一樣的, 遞迴式就是 A(n) = 4A(n/2)), A(1)=2
樓上說的很有道理數學式這樣列但電腦在算的時候應該會左右都遞回吧？只是發問 我也不是很確定＝ ＝
我的想法也是跟evidence一樣電腦執行時應該是會做兩個遞回吧?2*rec(n/2)+2*rec(n/2)--(A)而這種應該只有作一個遞回?4*rec(n/2) --(B)不知道是不是這樣才對.....A式執行時間會是B式兩倍?
我之前寫的是運算的結果, 如果你要算的是執行時間, 那麼要考慮的就變成是operations的次數, 這樣的確會不同, 遞迴式也會完全不同; 譬如假設乘法和加法的cost都是1, 那第一個的遞迴式就是 A(n)=2A(n/2)+3, 另一個是 A(n)=A(n/2)+1
收到收到^^
張貼留言
5 則留言:
2*rec(n/2)+2*rec(n/2) = 2*(2*rec(n/2)) = 4*rec(n/2), 所以那兩個是一樣的, 遞迴式就是 A(n) = 4A(n/2)), A(1)=2
樓上說的很有道理
數學式這樣列
但電腦在算的時候應該會左右都遞回吧？
只是發問 我也不是很確定＝ ＝
我的想法也是跟evidence一樣
電腦執行時應該是會做兩個遞回吧?
2*rec(n/2)+2*rec(n/2)--(A)
而這種應該只有作一個遞回?
4*rec(n/2) --(B)
不知道是不是這樣才對.....
A式執行時間會是B式兩倍?
我之前寫的是運算的結果, 如果你要算的是執行時間, 那麼要考慮的就變成是operations的次數, 這樣的確會不同, 遞迴式也會完全不同; 譬如假設乘法和加法的cost都是1, 那第一個的遞迴式就是 A(n)=2A(n/2)+3, 另一個是 A(n)=A(n/2)+1
收到收到^^
張貼留言