我是小小強檐迟，這是我的第4篇原創(chuàng)文章俺泣，閱讀需要大約10分鐘。
題目
LintCode:斐波納契數(shù)列
描述
查找斐波納契數(shù)列中第 N 個數(shù)蜓氨。
所謂的斐波納契數(shù)列是指：
前2個數(shù)是 0 和1 圆恤。
第 i 個數(shù)是第i-1個數(shù)和第i-2 個數(shù)的和突倍。
斐波納契數(shù)列的前10個數(shù)字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
樣例
給定 1，返回0
給定 2盆昙，返回1
給定10羽历，返回 34
實現(xiàn)
遞歸實現(xiàn)
- java代碼
class Solution {
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
- 結果分析
結果：結果不盡人意，速度非常慢淡喜，甚至沒有通過 LintCode 的評測秕磷。
分析：這種遞歸不同于一般的遞歸，在 n 較大時炼团，兩次遞歸調用中存在大量的重復運算澎嚣，導致速度非常慢。
非遞歸實現(xiàn)
- java代碼
class Solution {
public int fibonacci(int n) {
if(1==n)
return 0;
if(2==n)
return 1;
int a=0;
int b=1;
int sum=0;
while(n>2)
{
sum=a+b;
a=b;
b=sum;
n--;
}
return sum;
}
}
- 結果分析
結果：經測試 C++ 最快可以以 10ms 輕松通過 LintCode 的評測瘟芝。
分析：時間復雜度為 o(n) 易桃，空間復雜度為 o(1) ，效果不錯锌俱。
細節(jié)：使用 while 代替 for 節(jié)省了一個 Int(4Byte) 的空間晤郑。
