深入剖析斐波拉契數列

前言

動態規劃作為一種非常經典的一類演算法，不僅在解決實際問題當中有很多實際的應用，同時通常也是面試的一個重點，本篇文章一步步剖析動態規劃的基本原理，通過斐波拉契數列問題（優化時間復雜度從\(O(2^n)\)到O(n)再到O(log(n))）一步一步帶你從最基本的原理弄懂動態規劃，我們首先分析斐波拉契數列問題，然后在分析問題的時候慢慢的深入動態規劃，

斐波拉契數列

斐波拉契數列的定義如下：

\[F_0 = 0 \]

\[F_1 = 1 \]

\[F_n = F_{n - 1} + F_{n- 2} \]

就是斐波那契數列由0和1開始，之后的斐波那契數就是由之前的兩數相加而得出，比如說在斐波拉契數列當中第一個數為0，第二個數為1，因此第三個數為前面兩個數之和，因此第三個數為1，同理第四個數是第二個數和第三個數之和，因此第四個數為2，下面就是斐波拉契數的變化：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ....

斐波拉契數列——遞回法

現在我們的問題是要你求第n個斐波拉契數，這個問題還是比較簡單的，很容易想到這就是一個可以遞回解決的問題，在公式\(F_n = F_{n - 1} + F_{n-2}\)當中也容易看出應該使用遞回，現在要確定的就是遞回終止條件，

如果n == 0則回傳0，如果n == 1則回傳1，這就是遞回終止條件，

確定完遞回終止條件之后我們很容易寫出下面這樣的代碼：

public class Fibonacci {

  public static int fibonacci(int n) {
    if (n <= 1)
      return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

  public static void main(String[] args) {
    System.out.println(fibonacci(6));
  }
}

當我們求第6個斐波拉契數的時候，函式fibonacci的呼叫程序如下所示：

我們在呼叫fibonacci(6)的時候他會呼叫：[fibonacci(5)和fibonacci(4)]，然后fibonacci(5)會呼叫[fibonacci(4)和fibonacci(3)]，fibonacci(4)會呼叫[fibonacci(3)和fibonacci(2)]......

我們容易發現我們在函式呼叫的程序當中存在重復，比如下圖兩個相同的部分表示對fibonacci(4)重新計算，因為他們的呼叫樹都是一樣的：

這種使用遞回的方式計算斐波拉契數列的時間和空間復雜度都是\(O(2^n)\)，

斐波拉契數列——陣列法優化時間復雜度

既然是重復計算那么我們是否可用避免重復計算呢？在計算機一種常見的做法就是空間換時間，我們可以將之前計算的資料存下來，比如我們用陣列fib[]存盤我們計算得到的結果，fib[i] = fibonacci(i) ，那么根據斐波拉契數列的公式我們可以知道：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

當我們通過陣列存盤中間計算的資料的時候，我們應該使用什么樣的演算法進行計算呢？

在上面的圖片當中比如我們要計算綠色框對應的資料，根據公式：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

我們知道綠色框依賴它前面的兩個資料，因此我們在計算fib[i]的時候，需要提前將前面兩個它依賴的資料計算好，因此我們可以從左至右計算fib陣列，這樣的話我們在計算第n個fib數的時候前面n - 1個fib數已經計算好了，

因此我們的代碼可以像下面這樣：

public static int fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    // 進行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 從前往后遍歷得到 fib 陣列的結果
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

這種方式我們得到的時間和空間復雜度都降為了O(n)，

斐波拉契數列——陣列法優化空間復雜度

根據上面的分析我們可以知道，我們在計算第n個斐波拉契數的時候僅僅依賴它前面的兩個資料，因此我們無需用一個資料將所有的資料都保存下來，我們可以只用兩個變數保存他前面的兩個值即可，然后在進行for回圈的時候不斷進行更新就行了，

public static int fibonacci(int n) {
    if (n <= 1)
        return n;
    // 進行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 從前往后遍歷得到 fib 的結果
    for (int i = 2; i <= n; i++) {
        fib = a + b;
        a = b;
        b = fib;
    }
    return fib;
}

這樣我們的時間復雜度為O(n)空間復雜度就降低到了O(1)，

斐波拉契數列——矩陣乘法優化時間復雜度

我們已經知道斐波拉契數列的公式為：

\[fib[i] = fib[i - 1] + fib[i - 2], i \ge 2 \]

\[fib[n + 2] = fib[i + 1] + fib[i] \]

又因為：

\[fib[n + 1] = fib[n + 1] \]

根據上面的公式，我們根據矩陣乘法原理可以得到：

我們將n - 1得到：

我們不停的對上式最右側公式進行展開可以得到

從上式看，我們如果想求fib[n]的值，需要計算矩陣的冪，如果我們直接計算的話，時間復雜度為達到O(n)，但是我們希望能夠將時間復雜度降低到O(log(n))，在正式求解矩陣冪之前，我們先思考一個問題，如何在計算\(a^n\)時將時間復雜度降低到O(log(n))，

快速計算整數冪

首先我們先明確我們的目標：在計算\(a^n\)時將時間復雜度降低到O(log(n))，這個問題我們可以直接使用一個回圈就可以解決，但是時間復雜度為O(n)：

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
    public static int pow(int base, int n) {
        int ans = 1;
        for (int i = 0; i < n; i++)
            ans *= base;
        return ans;
    }

我們知道計算機在進行運算的時候都是采用2進制進行運算，所有的正整數如果是2的整數次冪的話，資料的二進制當中只有一個為為1，其余位置為0，

我們知道一個資料用二進制表示只有某些位置為0，某些位置為1，那么一個整數一定可以用若干個整數相加得到，而且這些整數滿足2的整數次冪，比如下圖中的7 = 1 + 2 + 4：

同樣的我們需要求解的\(2^n\)上的n也是可以通過加法得到，比如說\(2^7 = 2^1 * 2^2 * 2^4 = 2^{(1 + 2 + 4)}\)，因此我們可以使用下面的代碼進行快速冪的求解：

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {
    if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 第i個位元位置上是否為 1 如果為 1 就需要進行乘法運算
      // 這就相當于 ans *= base^i
      if (((n >> i) & 1) == 1) {
        ans *= base; // 這就相當于 冪相加 可以仔細分析上面的 2^7 的運算方式
      }
      // base 的變化情況為 base^1, base^2, base^3, base^4, ...
      // 比如說當 base 為 2 時，base 的變化情況為 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

斐波拉契資料列矩陣乘法的快速冪

首先在我們計算當中需要進行一個2x2的矩陣乘法運算，首先我們先定義一個簡單的2x2矩陣乘法運算，

  /**
   * 這里為了簡單期間，因為我們的矩陣乘法是 2x2 的
   * 所以可以直接做這樣的簡單的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {
    int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

我們現在來看我們使用矩陣快速冪得到斐波拉契數列的結果：

public static int fibonacci(int n) {
    if (n <= 1) return n;
    // 這個函式的作用是得到前面提到的矩陣的 n 次冪的結果
    int[][] mm = fibMatrixPower(n); // 這個函式的具體實作在下面
    // 根據下圖當中的公式容易知道我們最侄訓傳的結果就是 mm[1][0] 因為 fib[1] = 1 fib[0] = 0
    return mm[1][0];
}

public static int[][] fibMatrixPower(int n) {
    // 這個矩陣是根據上圖我們的公式得到的
    int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
        return baseMatrix;
    // 初始化為單位矩陣 如果是整數冪 初始化為 1
    // 這里初始化為單位矩陣的目的是因為單位矩陣和任何矩陣
    // 相乘結果都為原矩陣
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
        // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行矩陣乘法運算
        if (((n >> i) & 1) == 1) {
            // 進行矩陣乘法運算 相當于整數冪的時候數值乘法
            ans = matrixMultiply(ans, baseMatrix);
        }
        // 進行矩陣乘法運算求矩陣頻發 相當于整數冪的時候數值乘法 求數值的平方
        baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }
    return ans;
}

以上就是本文關于求解斐波拉契數列的各種方法，完整代碼如下：

public class Fibonacci {

  public static int fibonacci1(int n) {
    if (n <= 1)
      return n;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
  }

  public static int fibonacci2(int n) {
    if (n <= 1)
      return n;
    int[] fib = new int[n + 1];
    // 進行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 從前往后遍歷得到 fib 陣列的結果
    for (int i = 2; i <= n; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
  }

  public static int fibonacci3(int n) {
    if (n <= 1)
      return n;
    // 進行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 從前往后遍歷得到 fib 的結果
    for (int i = 2; i <= n; i++) {
      fib = a + b;
      a = b;
      b = fib;
    }
    return fib;
  }

  /**
   * 這個函式的目的是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {
    if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行乘法運算
      // 這就相當于 ans *= base^i
      if (((n >> i) & 1) == 1) {
        ans *= base;
      }
      // base 的變化情況為 base^1 base^2 base^3 ...
      // 比如說當 base 為 2 時，base 的變化情況為 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

  public static int pow(int base, int n) {
    int ans = 1;
    for (int i = 0; i < n; i++)
      ans *= base;
    return ans;
  }

  /**
   * 這里為了簡單期間，因為我們的矩陣乘法是 2x2 的
   * 所以可以直接做這樣的簡單的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {
    int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

  public static int[][] fibMatrixPower(int n) {
    int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
      return baseMatrix;
    // 初始化為單位矩陣 如果是整數冪 初始化為 1
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
      // 這個右移的目的是查看 n 對應的位置上是否為 1 如果為 1 就需要進行矩陣乘法運算
      if (((n >> i) & 1) == 1) {
        ans = matrixMultiply(ans, baseMatrix);
      }

      baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }

    return ans;
  }

  public static int fibonacci(int n) {
    if (n <= 1) return n;
    int[][] mm = fibMatrixPower(n);
    return mm[1][0];
  }

  public static void main(String[] args) {
    System.out.println(fibonacci1(1));
//    System.out.println(power(2, 8));
//    System.out.println(power(2, 8));
    System.out.println(fibonacci(1));
  }
}

總結

我們現在來重新捋一下我們在上面學習斐波拉契數列的思路：

首先我們用于解決斐波拉契數列的方法是遞回法但是這個方法有一個很大的問題，就是計算某個斐波拉契數的時候它依賴于它前面的斐波拉契數（這個程序相當于將一個大問題劃分成若干個小問題），這個依賴會導致我們進行很多重復的運算，為了解決這個問題我們用到了陣列法，這其實就是一個用空間換時間的方法，用陣列將前面計算你的結果存盤下來，避免重復計算，

通過分析我們公式，我們發現我們的資料依賴關系，我們在計算某個斐波拉契數的時候只需要依賴它前面的兩個斐波拉契數，因此我們不用存盤我們計算的每一個斐波拉契數，只需要保存兩個值即可，這就是我們優化陣列法的原理，

最后我們通過快速矩陣冪的方法將我們的時間復雜度從O(n)降低到了O(long(n))，這個方法其實帶有一定的技巧性，在大多數動態規劃的演算法當中我們用不到它，也就是說它的普適性并不強，

從上面的分析我們可以總結我們在使用動態規劃時的大致思路：

將大問題劃分成小問題，小問題繼續劃分......，學術一點的話說就是重疊子問題，
是否存在重復計算，如果存在使用空間換時間的方法進行優化，這是動態規劃一個非常重要的點，
是否能夠對陣列的空間復雜度進行優化，

在本篇文章當中主要和大家一起從0開始剖析斐波拉契數列問題，有幾個優化程序，整體的內容還是比較多的，希望大家有所識訓，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）

更多精彩內容合集可訪問專案：https://github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多計算機（Java、Python、計算機系統基礎、演算法與資料結構）知識，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499472.html

標籤：其他

上一篇：深入剖析多重背包問題（下篇）

下一篇：HTML和CSS、JavaScript規范第一部分（CSS部分）