h*****g
发帖数: 312 | 1 【 以下文字转载自 Quant 讨论区 】
发信人: salientxu (salientxu), 信区: Quant
标 题: fibonacci recursion
发信站: BBS 未名空间站 (Wed Aug 4 16:39:13 2010, 美东)
算fibonacci number 的resursion
int F(int n)
{ if (n==0) return 1;
if(n==1) return 1;
return F(n-1)+F(n-2);}
这个算法的空间复杂度是多少？ |
l*********8
发帖数: 4642 | 2 O(2^n)
每次递归要产生两个栈去调用下一层递归函数。 总共N-1层
【在 h*****g 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: salientxu (salientxu), 信区: Quant
: 标 题: fibonacci recursion
: 发信站: BBS 未名空间站 (Wed Aug 4 16:39:13 2010, 美东)
: 算fibonacci number 的resursion
: int F(int n)
: { if (n==0) return 1;
: if(n==1) return 1;
: return F(n-1)+F(n-2);}
: 这个算法的空间复杂度是多少？
|
m*********a
发帖数: 47 | 3 think again..
【在 l*********8 的大作中提到】
: O(2^n)
: 每次递归要产生两个栈去调用下一层递归函数。 总共N-1层
|
l*********8
发帖数: 4642 | 4 哦， O(n)
栈的深度
thanks
【在 m*********a 的大作中提到】
: think again..
|
h*****g
发帖数: 312 | 5 详细说说
【在 l*********8 的大作中提到】
: 哦， O(n)
: 栈的深度
: thanks
|
B******5
发帖数: 4676 | 6 栈层数最多到n，不会更深
【在 h*****g 的大作中提到】
: 详细说说
|
y**********u
发帖数: 6366 | |
g*********e
发帖数: 14401 | |
