斐波那契数列

递归方法

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)。