斐波那契數(shù)列，其最開(kāi)始的幾項(xiàng)是0疚鲤、1锥累、1、2集歇、3桶略、5、8、13删性、21亏娜、34…… ，后面的每一項(xiàng)是前兩項(xiàng)之和蹬挺，事實(shí)上维贺，斐波那契在數(shù)學(xué)上有自己的嚴(yán)格遞歸定義。

f0 = 0
f1 = 1
f(n) = f(n-1) + f(n-2)

斐波那契數(shù)列其實(shí)有很多有趣的性質(zhì)巴帮，比如你拿斐波那契里每項(xiàng)數(shù)為半徑繪制1/4圓弧溯泣，你就會(huì)得到著名的黃金螺旋線。

在這里插入圖片描述

在這里插入圖片描述

另外斐波那契數(shù)還有一個(gè)神奇的性質(zhì)肢簿，f(n-1)/f(n)約等于黃金分割比例，n越大蜻拨，其越接近黃金分割比0.6180339887…… 池充。

扯遠(yuǎn)了，回到今天的正題缎讼，如何求斐波那契數(shù)列第n項(xiàng)收夸，如果作為面試題的話，也可以考察候選人很多方面血崭，比如遞歸卧惜、優(yōu)化、數(shù)學(xué)…… 當(dāng)然現(xiàn)在大廠面試時(shí)很大可能也不會(huì)直接出斐波那契了夹纫，而是可能出現(xiàn)其變形咽瓷，文末會(huì)給出幾個(gè)相關(guān)參考題。

求解斐波那契數(shù)列第n項(xiàng)有很多種方式

遞歸求解

根據(jù)其遞歸定義捷凄，我們很容易寫(xiě)出以下遞歸函數(shù)來(lái)計(jì)算斐波那契第n項(xiàng)忱详。

    private static long fibonacci(int n) {
        if (n == 0) {
            return 0L;
        }
        if (n == 1) {
            return 1L;
        }
        return fibonacci(n-1) + fibonacci(n-2); 
    }

雖然按其數(shù)學(xué)定義來(lái)看围来，代碼是沒(méi)問(wèn)題跺涤，但這種實(shí)現(xiàn)效率非常低，存在著大量的重復(fù)計(jì)算监透，不信你用你自己電腦執(zhí)行下fibonacci(30) 試試桶错！ 哦，對(duì)了胀蛮，如果面試官讓你分析下上述代碼的時(shí)間復(fù)雜度院刁，你會(huì)分析嗎？粪狼？

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

像上圖中退腥，fib(3) fib(2) 被重復(fù)計(jì)算多次任岸，實(shí)際上對(duì)于任意n，其n-2節(jié)點(diǎn)都會(huì)出現(xiàn)在其左右子樹(shù)中狡刘。大致看起來(lái)遞歸求斐波那契數(shù)列的時(shí)間復(fù)雜度為O(2^n)享潜，這個(gè)也不是精確上界，精確證明見(jiàn)遞歸求解斐波那契數(shù)列的時(shí)間復(fù)雜度——幾種簡(jiǎn)潔證明
當(dāng)然遞歸版本也有有方法優(yōu)化的嗅蔬，我們之前打ACM的時(shí)候有種方法叫做記憶化搜索剑按，其本質(zhì)上就是把計(jì)算結(jié)果緩存下來(lái)，下次用的時(shí)候就直接取澜术，而不是重復(fù)計(jì)算艺蝴，這樣可以避免上述代碼中大量的重復(fù)計(jì)算，可以將其時(shí)間復(fù)雜度從O(2^n) 降至 O(n)鸟废。針對(duì)上面代碼的改動(dòng)也很簡(jiǎn)單猜敢，你可以自己試試（提示：就是加個(gè)全局?jǐn)?shù)組保證下結(jié)果）。

遞推求解

我們?cè)诮鉀Q問(wèn)題的時(shí)候盒延，逆向思維也很重要锣枝，逆向思維往往能找到更高效直接的解決方案。上述遞歸的方式其實(shí)是從后往前計(jì)算兰英，事實(shí)上我們可以從前往后計(jì)算撇叁。居然我們已知f0和f1，那我們就可以算出f2畦贸，緊接著算出f3 f4陨闹，一直到fn。

    private static long fibonacci(int n) {
        long[] fb = new long[n+1];
        fb[1] = 1;
        for (int i = 2; i <= n; i++) {
            fb[i] = fb[i-1] + fb[i-2];
        }
        return fb[n];
    }

不過(guò)上述代碼依舊有優(yōu)化空間薄坏。我們計(jì)算fb[i]只需要fb[i-1]和fb[i-2]兩項(xiàng)即可趋厉，是不是0到i-3都白存了！其實(shí)只需要保存長(zhǎng)度為2的滑動(dòng)窗口即可胶坠，優(yōu)化后代碼如下：

    private static long fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        long fa = 0L;
        long fb = 1L;
        long fc = fa + fb;
        for (int i = 2; i < n; i++) {
            fc = fa + fb; 
            fa = fb;
            fb = fc;
        }
        return fc;
    }

比內(nèi)公式

其實(shí)斐波那契第n項(xiàng)是有計(jì)算公式的君账，稱為比內(nèi)公式，如下：

在這里插入圖片描述

矩陣冪運(yùn)算

上面已經(jīng)說(shuō)了比內(nèi)公式有低效和精度損失的問(wèn)題珍特，我這里當(dāng)然有更牛x的方案了，那就是借助矩陣的運(yùn)算來(lái)解決魔吐，借助如下公式扎筒，我們可以計(jì)算出斐波那契的第n項(xiàng)。

在這里插入圖片描述

在這里插入圖片描述

>>fb = [1,1;1,0]
fb =
   1   1
   1   0

>>fb^10
ans =
   89   55
   55   34
   
>>fb^30
ans =
   1346269    832040
    832040    514229

小學(xué)三年級(jí)的時(shí)候我們學(xué)過(guò)求n次方的快速冪算法骨宠，可以把求n次方的時(shí)間復(fù)雜度從O(n)降低到O(log(n))，對(duì)于矩陣我們當(dāng)然也可以用快速冪算法(不知道快速冪的同學(xué)可以去復(fù)習(xí)下了)相满。

    // 快速求矩陣的n次方  
    private static long[][] pow(long[][] matrix, int n) {
        if (n == 1) {
            return matrix;
        }
        long[][] res = pow(matrix, n/2);
        res = multi(res, res);
        if (n%2 == 1) {
            res = multi(res, matrix);
        }
        return res;
    }
    // 兩個(gè)矩陣相乘 
    private static long[][] multi(long[][] m1,  long[][] m2) {
        long[][] res = new long[2][2];
        res[0][0] = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
        res[0][1] = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
        res[1][0] = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
        res[1][1] = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];
        return res;
    }
    
    public static void main(String[] args) {
        long[][] fb = {{1,1},{1,0}};
        long[][] res = pow(fb, 10);
        System.out.println(res[0][1]);
    }

上述幾種解法把時(shí)間復(fù)雜度從O(2^n)降低到了O(log(n))层亿，實(shí)際上還有O(1)的解法。斐波那契數(shù)列其實(shí)是一個(gè)增長(zhǎng)很快的數(shù)列立美，n用不了多大就會(huì)超過(guò)int甚至long所能表示的范圍(n大概幾十就會(huì)溢出)匿又，所以可以直接存下來(lái)，用的時(shí)候直接取建蹄，用空間換時(shí)間碌更，從而達(dá)到O(1)的時(shí)間復(fù)雜度。

面試題擴(kuò)展

求斐波那契第n項(xiàng)雖然看起來(lái)很基礎(chǔ)洞慎，但它也有著很高級(jí)的解法痛单，平凡中蘊(yùn)藏著不凡。事實(shí)上劲腿，你現(xiàn)在出去面試旭绒，大概率不會(huì)遇到面試官直接問(wèn)你斐波那契，而是其變形題或是和其他內(nèi)容融合的題焦人，比如：

1. 你每次可以上1級(jí)臺(tái)階挥吵，或者2級(jí)臺(tái)階，問(wèn)：上到第n級(jí)臺(tái)階總共有多少種不同的路徑垃瞧？
2. fib(i)對(duì)應(yīng)的是斐波那契的第i項(xiàng)蔫劣，找到所有第fin(i)個(gè)素?cái)?shù)(i<=20)坪郭，比如fib(20)是6765个从，第6765個(gè)素?cái)?shù)是67931。

歡迎關(guān)注我的面試專欄面試題精選，永久免費(fèi) 持續(xù)更新嗦锐，本專欄會(huì)收集我遇到的比較經(jīng)典面試題嫌松，除了提供詳盡的解法外還會(huì)從面試官的角度提供擴(kuò)展題，希望能幫助大家找到更好的工作奕污。另外萎羔，也征集面試題，如果你遇到了不會(huì)的題 私信告訴我碳默，有價(jià)值的題我會(huì)給你出一篇博客。
本文來(lái)自https://blog.csdn.net/xindoo