Fibonacci数的迭代算法

September 30, 2017
算法

使用迭代算法求斐波那契数列,

时间复杂度O(n),空间复杂度O(1)。

int f(int n)
{
	int f1 = 1, f2= 0;
    while(--n){
        f1 = f1+f2; // f(n) = f(n-1)+f(n-2)
        f2 = f1-f2;	// f(n-1) = f(n)-f(n-2) 
    }
    return f1;
}