斐波那契数列

xiaoxiao2021-03-01  6

递归方法

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;//Fib(0), Fib(1) while(0 < n--) { y = x + y; x = y - x; } return x; }

循环n次,时间复杂度为O(n),仅需2个int变量存储,空间复杂度为O(1)。

转载请注明原文地址: https://www.6miu.com/read-3200255.html

最新回复(0)