作者assassin88 (2010)
看板Grad-ProbAsk
标题[理工] [DS]-又是时间复杂度......
时间Sun Jan 17 18:52:23 2010
如果题目给的 code 如下：
void R(int n)
{ if (n <= 1)
return 2;
else
return (2*R(n/2) + 2*R(n/2));
}
请问复杂度是多少？
我式子列这样↓
T(n) = 2T(n/2) + 1
T(1) = 1
算出来复杂度为Θ(n)，但是答案是给Θ(nlgn)，请问我式子列错吗？
请指导..复杂度好难算..有什麽比较好的技巧吗？
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.57.105.93
1F：推 chenbojyh:我个人是觉得你算的结果没错 01/17 18:55
2F：推 polomoss:Θ(n) 01/17 21:31
3F：推 yesa315:同上 01/17 21:43
4F：→ taitin:用老大定理其实还蛮多题可以解的 01/17 22:54