递归方法
int Fib(
int n)
{
if(n==
0)
return 0;
else if(n==
1)
return 1;
else
return fibo(n-
1)+fibo(n-
2);
}
在递归过程中重复计算了之前已经计算出结果的项,。时间复杂度为O(n^2)。
改进后的迭代方法
x 表示前2项,y 表示前一项,z 表示当前项,即有 z=x+y。x 和 y 向前推进一位,即 y 到达原来的 z 位置,x 到达 原来的 y 位置,即将 z 与 y 交换,z 再与 x 交换。
简化的迭代方法
其实并不需要 z 这个临时变量,也不需要交换,赋值后即可表示。y 推进一位(即等于 z,由之前公式可得:z = x + y)即:新y = 原x + 原y,x 推进一位(即等于原y的值,由之前公式可得:原y = 新y - 原x)即:新x = 新y - 原x。
代码如下:
Fib(
int n)
{
x =
0; y =
1;
while(
0 < n--)
{
y = x + y;
x = y - x;
}
return x;
}
循环n次,时间复杂度为O(n),仅需2个int变量存储,空间复杂度为O(1)。