---
title: '演算法 - 複雜度分析'
disqus: kyleAlien
---

演算法 - 複雜度分析
===

## OverView of Content

[TOC]

## 模型效能預測

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

### 建模 - 實例大小重要性

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

| 問題大小 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^2^ + 0.000563 N*

> 成長率的數：N^2^
> 結論：高估耗時

* 對數公式： *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)**：檔案變大大，放在硬碟中，乘坐飛機的時間仍是一樣的，所以並不會因為檔案變大而加大時間

> 

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

### BIG O - 最差

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

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

* 常見的有 O(1)、O(n)、O(n\*m)、O(n^2^)、O(log N)、O(2^N^)...

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

> 

* 常見的有 O(1)、O(n)、O(n\*m)、O(n^2^)、O(log N)、O(2^N^)...

### BIG Theta

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

> 

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

> eg. 將 2 維陣列 O(N^2^) 視為 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);
        }

:::danger

* 空間複雜度陷阱：

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

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

                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^2^) 好就可以了**
:::success
* 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^)`

:::warning
* O(B^2^ + 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)
:::success
* 雖然最終算出 Big O 就是 O(2X) 但是 **由於在發生後 ++很長時間才會再發生++，所以期待價是可以被平攤的 :smile:**

* 這發生在每次會拓展兩倍 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^3^ = 8 -> log~2~^8^ = 3 （答案是 3 次）
>
> log~2~^N^ = k (k 是答案，所有 log~2~^N^ 就是搜尋次數，BIG O 就是 O(log~2~^N^))
> -
> 2^k^ = N (N 是陣列長度)

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

:::info
* Log 的 **底數對於 BigO 來說並不重要**
:::

### 遞迴執行時間

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

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

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

| 層數 | 節點數 | 表示法 |
| -------- | -------- | -------- |
| 1 | 1 | 2^0^ |
| 2 | 2 | 2^1^ |
| 3 | 4 | 2^2^ |
| 4 | 8 | 2^3^ |
| 5 | 16 | 2^4^ |

如果是 N 層的遞迴就會有 2^0^ + 2^1^ + 2^2^ + 2^3^ + 2^4^ + ... + 2^N^，也就是 **2^N+1^ -1 個節點**
> 用二進位來看就很明顯
> 1111 就是 10000 - 1，也就是 2^5^ - 1

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

> 

:::warning
* 2 元樹的空間複雜度

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

### 常見複查度 - 比較

常見複查度比較，如下圖

> 

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

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

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`