斐波那契數(shù)列算法（分類(lèi)：）斐波那契數(shù)列算法斐波那契數(shù)列問(wèn)題是算法學(xué)習(xí)者必然接觸到的問(wèn)題，作為經(jīng)典問(wèn)題，斐波那契數(shù)列算法首次接觸時(shí)一般是作為遞歸算法的案例教程。然而遞歸解決斐波那契，其效率低的令人發(fā)指，有人算出其時(shí)間復(fù)雜度為O(2^n)。指數(shù)級(jí)時(shí)間復(fù)雜度。如果面試的時(shí)候面試官問(wèn)你斐波那契的求解方法，你來(lái)一個(gè)遞歸求解，基本上可以說(shuō)，你已經(jīng)game over了。下面是斐波那契的4種算法：
斐波那契數(shù)列算法
斐波那契數(shù)列算法
1.遞歸 時(shí)間復(fù)雜度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.循環(huán) 時(shí)間復(fù)雜度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.矩陣求解 時(shí)間復(fù)雜度O(logn)斐波那契數(shù)列算法
斐波那契的遞推公式可以表示成如下矩陣形式，所以其所以根據(jù)矩陣的分治算法，可以在O(logn)時(shí)間內(nèi)算出結(jié)果。筆試問(wèn)題：對(duì)于斐波拉契經(jīng)典問(wèn)題，我們都非常熟悉，通過(guò)遞推公式F(n) = F(n - 1) + F(n - 2)，我們可以在線性時(shí)間內(nèi)求出第n項(xiàng)F(n)，現(xiàn)在考慮斐波拉契的加強(qiáng)版，我們要求的項(xiàng)數(shù)n的范圍為int范圍內(nèi)的非負(fù)整數(shù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法，計(jì)算第n項(xiàng)F(n)。第一個(gè)斐波拉契數(shù)為F(0) = 1。
4.公式求解 時(shí)間復(fù)雜度O(1)；歡迎觀看斐波那契數(shù)列算法的。（更新時(shí)間：2017.3.27 15：41）
- 斐波那契數(shù)列與股市
- 斐波那契數(shù)列與股市（分類(lèi)：）斐波那契數(shù)列與股市時(shí)間周期理論是股價(jià)漲跌的根本原因之一，斐波那契數(shù)列與股市它能夠解釋大多數(shù)市場(chǎng)漲跌的奧秘。......
- 斐波那契數(shù)列算法
- 斐波那契數(shù)列算法（分類(lèi)：）斐波那契數(shù)列算法斐波那契數(shù)列問(wèn)題是算法學(xué)習(xí)者必然接觸到的問(wèn)題，作為經(jīng)典問(wèn)題，斐波那契數(shù)列算法首次接觸時(shí)一般是......
- 斐波那契數(shù)列的故事
- 斐波那契數(shù)列的故事（分類(lèi)：）斐波那契數(shù)列的故事斐波那契數(shù)列（Fibonacci sequence），斐波那契數(shù)列的故事又稱(chēng)黃金分割數(shù)列......
- 斐波那契數(shù)列的證明
- 斐波那契數(shù)列的證明（分類(lèi)：）斐波那契數(shù)列的證明斐波那契數(shù)列,“斐波那契數(shù)列”的發(fā)明者，斐波那契數(shù)列的證明是意大......
- 斐波那契數(shù)列的意義
- 斐波那契數(shù)列的意義（分類(lèi)：教學(xué)視頻） 斐波那契數(shù)列的意義“斐波那契數(shù)列”的發(fā)明者，是意大......
