斐波拉契数组
递归实现
public class Fibonacci {
// 使用递归实现,效率极低
public long fRecursive(int n) {
if (n <= 1) {
return n;
}
return fRecursive(n - 1) + fRecursive(n - 2);
}
}
使用循环实现
时间复杂度为O(n)
public class Fibonacci {
// 使用循环实现,最优实现
public long f(int n) {
if (n <= 1) {
return n;
}
long first = 0;
long second = 1;
long result = 0;
for (int i = 2; i <= n; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}
}
扩展
一只青蛙一次可以跳上1级台阶,也可以跳上2级,求青蛙跳上一个n级的台阶总共有多少种跳法?
分析:
网友评论