演算法 - 複雜度分析

OverView of Content

• 演算法 - 複雜度分析
  • OverView of Content
  • 模型效能預測
    • 建模 - 實例大小重要性
  • 時間複雜度
    • BIG O - 最差
    • BIG Omega - 最佳
    • BIG Theta
  • 空間複雜度
  • 複雜度表示
    • 去掉常數
    • 去掉非優勢項
    • 多步驟 - 加 & 乘
    • 平攤時間 - ArrayList
    • Log N 執行時間
    • 遞迴執行時間
    • 常見複查度 - 比較
  • Appendix & FAQ

模型效能預測

增加問題的實例大小，當到 達足夠大個實例時，就可以開發模型，並 實證模型做演算法執行時間表現的分級

建模 - 實例大小重要性

• 以下為結果雛形，透過雛形來 推算 (猜測、預估) 演算法公式

  問題大小 N	耗時 (秒)
  100	0.063
  1,000	0.565
  10,000	5.946

  • 接下來幾種建模公式來往上調整大小作測試，可以發現 ^1. 實例大小的重要性，^2. 公式中最成長率的數的影響

    • 線性公式： TL(N) = 0.000596 x N - 0.012833

      成長率的數：N
      結論：低估耗時

    • 二次公式： TQ(N) = 0.000000003206 x N² + 0.000563 N

      成長率的數：N²
      結論：高估耗時

    • 對數公式： TN(N) = 0.0000448 x N x log(N)

      成長率的數：N x log(N)
      結論：接近耗時

      問題大小 N	原先演算法耗時 (秒)	線性 TL	二次 TQ	對數 TL
      100	0.063	0.047	0.056	0.030
      1,000	0.565	0.583	0.565	0.447
      10,000	5.946	5.944	5.946	5.955
      100,000	65.391	59.559	88.321	74.438
      1,000,000	860.851	595.708	3769.277	893.257
      10,000,000	9879.44	5957.194	326299.837	10421.327

時間複雜度

• 複雜度重要性，舉例
  有個 1 TB 檔案急件要給朋友，那要用網路分享 (10hr) 的還是用現實中拿給朋友 (開車來回 6 hr) 呢 ? (不計成本)

  資料	驗算法	時間	複雜度表示
  1TB	網路分享	10hr	電子傳輸 O(s)
  1TB	飛機	6hr	實體給予 O(1)

• 電子傳輸 O(s)：檔案越大上傳的時間越多，s 是檔案大小

• 實體給予 O(1)：檔案變大大，放在硬碟中，乘坐飛機的時間仍是一樣的，所以並不會因為檔案變大而加大時間

  • 不管常數有多大，線性成長有多慢，線性成長最終都會超過常數

BIG O - 最差

• Big O 表示的是最差成長率

• 學術中 Big O 用來表示時間的 上界 (upper bound)，代表該演算法最慢不會低於 Big O 數值，也就是該演算法的最差表現

• 常見的有 O(1)、O(n)、O(n*m)、O(n²)、O(log N)、O(2^N)…

BIG Omega - 最佳

• 學術中 BIG Omega 用來表示時間的 下界 (lower bound)，代表該演算法最快不會高於 Big Omega 數值，也就是該演算法的最佳表現

• 常見的有 O(1)、O(n)、O(n*m)、O(n²)、O(log N)、O(2^N)…

BIG Theta

• 其實就是將 BIG O & BIG Omega 結合在一起，並且兩者都成立

  • 業界有一些會把 BIG Theta & BIG O 合併一起看，因為大部分狀況下不會差到真的到達 BIG O

    eg. 將 2 維陣列 O(N²) 視為 O(N)

空間複雜度

• 空間複查主要是指，該 演算法實際占用的記憶體空間

• 常見的用法如下：表達方式依樣可以使用 BIG O

  1. 陣列

     ​​​​​​​​// 一維陣列
     ​​​​​​​​private void oneDimensional() {
     ​​​​​​​​    // 空間複雜度 O(i)
     ​​​​​​​​    for(int i = 0; i < 10; i++) {
     ​​​​​​​​        System.out.println(i);
     ​​​​​​​​    }
     ​​​​​​​​}
     
     ​​​​​​​​// 二維陣列
     ​​​​​​​​private void twoDimensional() {
     ​​​​​​​​    // 空間複雜度  O(i*j)
     ​​​​​​​​    for(int i = 0; i < 10; i++) {
     ​​​​​​​​        for(int j = 0; j < 10; j++) {
     ​​​​​​​​            System.out.println(i);
     ​​​​​​​​        }
     ​​​​​​​​    }
     ​​​​​​​​}
     

  2. 遞迴：stack 深度

     ​​​​​​​​private int sum(int num) {
     ​​​​​​​​    // 空間複雜度 O(x!)
     ​​​​​​​​    // x! = x + (x - 1) + (x - 2) + (x - 3) ... + 0
     ​​​​​​​​    if(num <= 0) {
     ​​​​​​​​        return 0;
     ​​​​​​​​    }
     ​​​​​​​​    return num + sum(num - 1);
     ​​​​​​​​}
     

     • 空間複雜度陷阱：

       遞迴占用空間複查度狀況是在 同一個方法中的棧 (一個方法就是一個棧，當跳出該方法後該棧就結束了)，詳細的要去看組合語言的指令

       但查看組合語言指令是非必要的

       ​​​​​​​​​​​​    private int sumTrap(int num) {
       ​​​​​​​​​​​​        int result = 0;
       
       ​​​​​​​​​​​​        // 空間複雜度 O(N)
       ​​​​​​​​​​​​        for(int i = 0; i < num; i++) {
       ​​​​​​​​​​​​            result += temp(i, i + 1);   // temp 當下就會計算出來，不會棧用到空間
       ​​​​​​​​​​​​        }
       
       ​​​​​​​​​​​​        return result;
       ​​​​​​​​​​​​    }
       
       ​​​​​​​​​​​​    private int temp(int a, int b) {
       ​​​​​​​​​​​​        return a + b;
       ​​​​​​​​​​​​    }
       

複雜度表示

去掉常數

• 在特定的輸入下 O(N) 的程式可以比 O(1) 執行的要快，由於這個原因我們可以把執行時間中的常數刪除 (因為它不太重要，影響到 成長率 的曲線不大，畢竟它是固定的)

  想想上面的例子 (飛機 & 上網分享)

• Big O 允許我們表達執行時間是如何擴展的，我們只要接受 O(N) 不一定永遠比 O(N²) 好就可以了

  • BIG O 重點是表達該演算法的 成長率

• 以下的例子兩個相同的 for 迴圈執行兩次每次執行 N，也就是 O(2N)，在演算法實際上就是 O(N)

  O(2N) 就是時間的擴展

  ​​​​    private final int[] array = {1, 2, 3, 4, 5, 6};
  
  ​​​​    private void twoForeach() {
  ​​​​        int min = Integer.MAX_VALUE;
  ​​​​        int max = Integer.MIN_VALUE;
  
  ​​​​        for(int n : array) {
  ​​​​            if(n < min) min = n;
  ​​​​        }
  
  ​​​​        for(int n : array) {
  ​​​​            if(n > max) max = n;
  ​​​​        }
  ​​​​    }
  
  ​​​​    private void oneForeach() {
  ​​​​        int min = Integer.MAX_VALUE;
  ​​​​        int max = Integer.MIN_VALUE;
  
  
  ​​​​        for(int n : array) {
  ​​​​            if(n < min) min = n;
  ​​​​            if(n > max) max = n;
  ​​​​        }
  ​​​​    }
  

去掉非優勢項

• 移除非重要的項，留下最大的項，因為 最大的項才是影響曲線的最大因素（當取數據越大，則大項的影響越重

• 去掉非優勢項 - 範例

  1. O(N^2^ + N + 1) => O(N^2^)
  2. O(N + log N) => O(N)
  3. O(5\*2^n^ + 1000N) => O(2^N^)
  • O(B² + A) 則不能被簡化，因為 A、B 的描述不同，無法在同一個基準線在說明

• 以下是常見的幾種 BIG O 曲線圖 (是有點角度的，這邊大概畫一下)

  

多步驟 - 加 & 乘

1. 乘法: 每次執行完一個操作時，另一個操作就要重複一次，這時就是使用乘法

   ​​​​// O(i*j)
   ​​​​    private void twoDimensional() {
   ​​​​        for(int i = 0; i < 10; i++) {
   ​​​​            for(int j = 0; j < 10; j++) {
   ​​​​                System.out.println(i);
   ​​​​            }
   ​​​​        }
   ​​​​    }
   

2. 加法: 如果是兩個相同的 來源則可以說是兩倍，若兩個不同的來源，則必須使用加法

   ​​​​// O(A+B)
   ​​​​    private void twoForeach() {
   ​​​​        for(int n : A_array) {
   ​​​​            if(n < min) min = n;
   ​​​​        }
   
   ​​​​        for(int n : B_array) {
   ​​​​            if(n > max) max = n;
   ​​​​        }
   ​​​​    }
   

平攤時間 - ArrayList

• 首先要知道 ArrayList 的大致實作

  1. 內部使用靜態 Array 存取數據

  2. 當到達指定容量時 (閥值)，就會使用 System.arraycopy 進行擴容

  3. 每次擴容都是上次容量的兩倍

  ​​​​1. 原本長度 N
  ​​​​2. 擴容 N * 2 = 2N
  ​​​​3. 將原本數據複製過去 N
  
  ​​​​總共發會時間 O(2N + N)
  

• 以 ArrayList 來說，每次容量翻倍 1、2、4、8、16、…、X，並且需要做 1、2、4、8、16、…、X 次複製

  而 1 + 2 + 4 + 8 + 16 + … + X 和約略是 2X (但不會大於 2X)，Big O 就是 O(2X)

  從右往左看（反著看）是 X + … + 16 + 8 + 4 + 2 + 1，每次減半到 1，最終可以發現 從 (X - 1) ~ 1 加起來會很接近 X

  X + X/2 + X/4 + X/8 + X/16 + … + 1 = O(2X)

  • 雖然最終算出 Big O 就是 O(2X) 但是 由於在發生後 很長時間才會再發生，所以期待價是可以被平攤的

  • 這發生在每次會拓展兩倍 cache 的算法中

  • 由於 Array 插入是可以被平攤的，所以其 BIG O 時間是 O(1)

Log N 執行時間

• 以二分法搜尋為例，每次都會將要搜索的來源除 2 ，最後就會比對到我們要尋找的目標

  ​​​​// 偽代碼
  
  ​​​​int[] array = {1, 2, 3, 4, 5, 6, 7, 8}
  
  ​​​​// 尋找 3
  
  ​​​​1. 比對 4：3 比 4 小搜尋 {1, 2, 3, 4}
  ​​​​2. 比對 2：3 比 2 大搜尋 {3, 4}
  ​​​​3. 比對 3：3 等於 3 找到答案
  ​​​​
  ​​​​// ----------------------------------------------------------------
  ​​​​N 為搜尋大小
  ​​​​N = 8
  ​​​​N = 4
  ​​​​N = 2
  ​​​​N = 1
  

  每次都是將原來大小除 2 ，反過來看就是乘多少次 2 可以到達原先陣列長度

  2³ = 8 -> log₂⁸ = 3 （答案是 3 次）

  log₂^N = k (k 是答案，所有 log₂^N 就是搜尋次數，BIG O 就是 O(log₂^N))

  2^k = N (N 是陣列長度)

• 在平衡 2 元樹下搜尋一個元素點所耗費的時間為 O(logN)，空間元素每次減半，那執行時間很可能就是 O(log N)

  • Log 的 底數對於 BigO 來說並不重要

遞迴執行時間

• 查看以下程式，它透過呼叫自身遞迴計算出結果

  ​​​​int f(int n) {
  ​​​​    if(n <= 1) {
  ​​​​        return 1;
  ​​​​    }
  ​​​​    return f(n - 1) + f(n - 2);
  ​​​​}
  

  每有一個節點，其底下都會有 2 個子節點，所以每層的節點數如下

  層數	節點數	表示法
  1	1	20
  2	2	21
  3	4	22
  4	8	23
  5	16	24

  如果是 N 層的遞迴就會有 2⁰ + 2¹ + 2² + 2³ + 2⁴ + … + 2^N，也就是 2^N+1 -1 個節點

  用二進位來看就很明顯
  1111 就是 10000 - 1，也就是 2⁵ - 1

  以照遞迴的模式進行大多數的時間消耗是 O(分支^深度)，二元樹就是 O(2^N)，M 元樹 (M^N)

  

  • 2 元樹的空間複雜度

    與 LogN 相反，如果演算法每次都會拓展 空間兩倍，這時計算時間就很可能會變成 O(2ⁿ)

常見複查度 - 比較

常見複查度比較，如下圖

• 在 1 小時又 8 分鐘裡 (68 * 60 = 4080，我們假設為 4096 秒)，假設一秒可以解決一個問題，以下是每個演算法可以解決的最大問題數量

  演算法複雜度	可解決問題數
  O(1)	跟時間無關，固定只能解決某個量的問題
  O(logN)	問題數量必須 < 24096
  O(N)	問題數量必須 < 4096
  O(NlogN)	問題數量必須 < 462
  O(N2)	問題數量必須 < 64
  O(N3)	問題數量必須 < 16
  O(2N)	問題數量必須 < 12
  O(N!)	問題數量必須 < 7

Appendix & FAQ

tags: 資料結構