斐波那契數(shù)列算法

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.循環(huán)    時間復雜度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)斐波那契數(shù)列算法

 斐波那契的遞推公式可以表示成如下矩陣形式，所以其所以根據(jù)矩陣的分治算法，可以在O(logn)時間內(nèi)算出結(jié)果。筆試問題：對于斐波拉契經(jīng)典問題，我們都非常熟悉，通過遞推公式F(n) = F(n - 1) + F(n - 2)，我們可以在線性時間內(nèi)求出第n項F(n)，現(xiàn)在考慮斐波拉契的加強版，我們要求的項數(shù)n的范圍為int范圍內(nèi)的非負整數(shù)，請設(shè)計一個高效算法，計算第n項F(n)。第一個斐波拉契數(shù)為F(0) = 1。

4.公式求解  時間復雜度O(1)；歡迎觀看斐波那契數(shù)列算法的。（更新時間：2017.3.27  15：41）