作者perry0627 (打败无敌)
看板Grad-ProbAsk
标题Re: [理工] [DS]-又是时间复杂度......
时间Thu Feb 4 02:17:03 2010
※ 引述《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