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;
}
使用迭代算法求斐波那契数列,
时间复杂度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;
}