作者numb4ujb (卷毛)
看板Grad-ProbAsk
标题[问题] 请问资料结构 Fib 费氏数
时间Thu Mar 19 17:48:59 2009
我想请问
费氏数 fib 的时间复杂度是多少呢!!?
void Fib(int n)
{
if (n <= 1)
return n;
else
return (Fib(n-1) + Fib(n-2));
}
脑筋突然转不过来 ..
希望能附上算式 感谢 ><
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.165.195.215
1F：→ rockpaulroll:用T(n)=T(n-1)+T(n-2)+1求时间复杂度吧 03/19 17:53
2F：→ rockpaulroll:阿错了 不好意思 没有加1 03/19 17:53
3F：→ rockpaulroll:特徵解:α^2-α+1=0 03/19 17:56
4F：推 lh132:用离散方式解递回=>O((1+sqrt(5)/2)^n) 03/19 17:57
5F：推 Sucker:似乎是用特性方程式解出来那条= = 03/19 17:57
6F：→ numb4ujb:感谢解答~ 好像有+1耶 是吗 因为非递回的执行次数@@? 03/19 17:58
7F：→ rockpaulroll:没有加1的原因是因为一直Recursive下去而没有做别的 03/19 18:01
8F：→ rockpaulroll:运算 03/19 18:01