斐波那契數列算法（分類：）斐波那契數列算法斐波那契數列問題是算法學習者必然接觸到的問題，作為經典問題，斐波那契數列算法首次接觸時一般是作為遞歸算法的案例教程。然而遞歸解決斐波那契，其效率低的令人發指，有人算出其時間復雜度為O(2^n)。指數級時間復雜度。如果面試的時候面試官問你斐波那契的求解方法，你來一個遞歸求解，基本上可以說，你已經game over了。下面是斐波那契的4種算法：
斐波那契數列算法
斐波那契數列算法
1.遞歸 時間復雜度O(2^n)
[java] view plain copy
int f(int n){
if(n == 1 || n == 2){
return 1;
return f(n-1) + f(n-2);
2.循環 時間復雜度O(n)
[java] view plain copy
public int f(int n) // write code here
int f0 = 1;
int f1 = 1;
int f2 = 0;
for(int i = 2; i < n; i++){
f2 = f0 + f1;
f0 = f1;
f1 = f2;
return f2;
3.矩陣求解 時間復雜度O(logn)斐波那契數列算法
斐波那契的遞推公式可以表示成如下矩陣形式，所以其所以根據矩陣的分治算法，可以在O(logn)時間內算出結果。筆試問題：對于斐波拉契經典問題，我們都非常熟悉，通過遞推公式F(n) = F(n - 1) + F(n - 2)，我們可以在線性時間內求出第n項F(n)，現在考慮斐波拉契的加強版，我們要求的項數n的范圍為int范圍內的非負整數，請設計一個高效算法，計算第n項F(n)。第一個斐波拉契數為F(0) = 1。
4.公式求解 時間復雜度O(1)；歡迎觀看斐波那契數列算法的。（更新時間：2017.3.27 15：41）
- 斐波那契數列與股市
- 斐波那契數列與股市（分類：）斐波那契數列與股市時間周期理論是股價漲跌的根本原因之一，斐波那契數列與股市它能夠解釋大多數市場漲跌的奧秘。......
- 斐波那契數列算法
- 斐波那契數列算法（分類：）斐波那契數列算法斐波那契數列問題是算法學習者必然接觸到的問題，作為經典問題，斐波那契數列算法首次接觸時一般是......
- 斐波那契數列的故事
- 斐波那契數列的故事（分類：）斐波那契數列的故事斐波那契數列（Fibonacci sequence），斐波那契數列的故事又稱黃金分割數列......
- 斐波那契數列的證明
- 斐波那契數列的證明（分類：）斐波那契數列的證明斐波那契數列,“斐波那契數列”的發明者，斐波那契數列的證明是意大......
- 斐波那契數列的意義
- 斐波那契數列的意義（分類：教學視頻） 斐波那契數列的意義“斐波那契數列”的發明者，是意大......
