※ 引述《assassin88 (2010)》之銘言：
: 如果題目給的 code 如下：
: void R(int n)
: { if (n <= 1)
: return 2;
: else
: return (2*R(n/2) + 2*R(n/2));
------ ------
1 2
: }
: 請問複雜度是多少？
: 我式子列這樣↓
: T(n) = 2T(n/2) + 1
: T(1) = 1
: 算出來複雜度為Θ(n)，但是答案是給Θ(nlgn)，請問我式子列錯嗎？
: 請指導..複雜度好難算..有什麼比較好的技巧嗎？
: 感謝
因為每次的recurrece都執行 O(1) 個指令
而且每次遞迴會縮減為 R( n/2 )
執行兩次 (如我的圖)
所以時間函數是 T(n) = 2 T( n/2 ) + O(1) , T(1) = O(1)
解複雜度的方法:
1. master method:
令 f(n) = O(1), a=2 , b=2
=> 取 c = lg 2 > 0
lg2 - c
=> f(n) = O(1) = O(n )
=> T(n) = O( n )
2. 代入法:
T(n) = 2 T(n/2)
2 2
= 2 T(n/ 2 )
k k
= ... = 2 T(n/2 )
令k = lg n
lg n lg2
=> T( n ) = 2 T(1) = n * O(1) = O( n )
有點忘了...希望沒錯能幫上忙囉^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.191.174