---
title: '演算法 - 效能分析'
disqus: kyleAlien
---

演算法 - 效能分析
===

## OverView of Content

技術分析與演算法的實作無關

[TOC]

## 演算法

### 何謂演算法

* 演算法就是按部就班解決問題的方法，那這個解決問題的方法可以有多個

> 

* 演算法具有以下特性

1. **相同的結論**：不同演算法解決問題，可得得出相同的結論

2. **可預測時間**：演算法基於固定流程進行，既然是固定流程就可以預測演算法的完成時間

:::success
* 演算法設計難點

演算法設計的主要挑戰是確保演算法的 ***正確性***，針對不同的輸入，要都可以輸出正確結果
:::

### 演算法 - 效能標準

* 判斷演算法的效率表準方法是 **計數演算法所需的 ==運算作業== (computing operation) 次數**，並且我們 **只關注 ==關鍵作業== (key operation)**；

**關鍵作業**：像是函數呼叫次數，比較次數、判斷測數... 等等

:::info
* 在這裡所謂的運算作業 **並不包含機械碼 (匯編語)**

1. 因為每個程式語言的特性不同，最後翻譯出來的機械碼會有所差異

2. 機械碼指令是針對不同硬體也不同的指令作業方式；在高級語言下一樣的程式，解析成機械碼會有不同結果

3. 機械碼的指令過於龐大
:::

## 串列中最大值

* 使用 for 迴圈在一個無序串列中取得一個最大值

    public int findMaxValue(int[] array) {
        int max = Integer.MIN_VALUE;

        for(int item : array) {
            if(item > max) {
                max = item;
            }
        }

        return max;
    }

> 

* `findMaxValue` 即為一個演算法，它的關鍵步驟在 ***比較*** (`>` 大於符號)，該運算符號被呼叫了 `N` 次 (也就是 `array.length` 陣列長)

:::warning
* `findMaxValue` 待解決問題

如果上面解法輸入是 `[]` array，則會回傳 `Integer.MIN_VALUE` 這並不正確；於是下面我們直接使用 `array[0]` 來做為初始值，**當空陣列時會拋出 `ArrayIndexOutOfBoundsException` 警告使用者**

            public int findMaxValue_2(int[] array) throws ArrayIndexOutOfBoundsException {
                    int max = array[0];

                    for (int i = 1; i < array.length; i++) {
                        int item = array[i];
                        if (item > max) {
                            max = item;
                        }

                        System.out.println("max: " + max);
                    }

                    return max;
                }

> 比較 `>` 的次數轉為 `N-1` 也算是小小的優化
:::

### 可預測演算法效能 - 模型

* 同樣是求一個 List 中的最大值，這是我們使用另一種演算法 (解法)，來觀察最佳強況 (best case)、最差情況 (worst case)

    // 演算法

    public int findMaxValue_3(int[] array) throws ArrayIndexOutOfBoundsException {
        for(int outSide : array) {
            
            boolean isMaxVal = true;    // 外邊先預設當前數就是最大數

            // 當前要比較的數
            System.out.println(outSide);

            for (int inside : array) {
                
                // 每次比較前列印，代表該演算法耗費時間的計算
                System.out.print(inside + " > " + outSide + " ?\n");

                if(inside > outSide) {
                    isMaxVal = false;    // 內部發現不是最大數，則修改
                    break;
                }
            }

            System.out.println("--------------");
            if(isMaxVal) {
                return outSide;
            }
        }

        return -1;
    }

1. 普通情況

        // 普通情況

        public static void main(String[] args) {
            int result;

            result = new ListMax().findMaxValue_3(new int[] {1, 5, 2, 9, 3, 4});

            System.out.println("finally result 3: " + result);
        }

> 

2. **最佳情況 base case**：指需要比較 *N* 次就可得出結論

        // 最佳情況 base case

        public static void main(String[] args) {
            int bestCase = new ListMax().findMaxValue_3(new int[] {9, 1, 5, 2, 3, 4});

            System.out.println("Best case: " + bestCase);
        }

> 

3. **最差情況 worst case**：需要 *(N^2^ + 3N - 2) / 2* 次的比較

        // 最差情況 worst case

        public static void main(String[] args) {
            int worstCase = new ListMax().findMaxValue_3(new int[] {1, 2, 3, 4, 5, 9});

            System.out.println("Worst case: " + worstCase);
        }

> 

* 隨著運算的 Array 變大，其最佳、最差值就會相當明顯

### 串列的最大兩數

* 這邊用另外一個 case 串列的最大兩數，同樣來看看 最佳、差狀況

    // 串列的最大兩數

    public int[] findMaxValueTwo(int[] array) throws ArrayIndexOutOfBoundsException {
        int large = array[0];
        int largeSecond = array[1];

        if(largeSecond > large) {    // 判斷兩值是否需要交換
            int tmp = largeSecond;
            largeSecond = large;
            large = tmp;
        }

        for(int i = 2; i < array.length; i++) {
            int curVal = array[i];
            
            if(curVal > large) {    // 第一個判斷
                int tmp = large;
                large = curVal;
                largeSecond = tmp;
    
            } else if(curVal > largeSecond) {    // 第二個判斷
                largeSecond = curVal;
            }
        }

        return new int[] {large, largeSecond};
    }


    public static void main(String[] args) {
        int[] largeTwo = new ListMax().findMaxValueTwo(new int[] {1, 5, 2, 9, 3, 4});

        System.out.println("Large two: " + Arrays.toString(largeTwo));
    }

> 

:::info
使用比較大小來計數
:::

* 最佳情況：***N - 1* 次**；

* 也就是指會進入第一個 if 判斷，不會有第二個判斷；

* 從 2 開始所以是 N - 2，再加上最一開始的比較 1，就是 N - 2 + 1；最終就是 *N - 1* 次

* 最差情況：***2N - 3* 次**

* 會有第一個判斷不成立，再進入第二個判斷；

* 從 2 開始，所以是 2 * (N - 2)，再加上最一開始的比較 1，就是 2 * (N - 2) + 1；最終就是 *2N - 3* 次

### 最佳演算法 - 考量點

* 額外的儲存需求

演算法是否需要複製原本的問題實例

* 程式設計負荷

程式長度

* 可變輸入

演算法改變輸入，但要維持相同輸出

* 速度

演算法的效率

## 對數 logarithm

對數 logarithm 就是 `log`，**log 為指數 (N!) 的反函數**，以計算機科學而言，log() 運算是以 2 為底居多

### 第二大數 - 錦標賽對數

* 錦標賽的比賽概念就很適合來呈現指數的運算行為 (綠色為最一開始比賽的分數，也就是 `[3, 1, 4, 1, 5, 9, 2, 6]`)

> 

1. 算出最大值：最簡單如同上面我們所運算，只 **需要 *N - 1* 次的比大小**

        private static final int[] tournament = new int[] {3, 1, 4, 1, 5, 9, 2, 6};

        public int findMax() {
            int result = tournament[0];

            for (int i = 1; i < tournament.length; i++) {
                int item = tournament[i];

                if (item > result) {    // tournament.length - 1 次
                    result = item;
                }
            }

            return result;
        }

2. 第二大值：如果有將每次比賽紀錄結果都紀錄下來，那找到第二高速度就很快；其實也就是形成了二元樹的狀態；

* 要求得第二大值只需要比較 2 次：**比較 2 次並不是巧合，其中存在規則**；

* 第一名的比較次數 3 次：**8 = 2^3^，也就是 2 ^比賽次數^**

* 第二名的比較次數 2 次：4 = 2^2^，**同樣是 2 ^比賽次數^**
> 第二名參賽者：`4`、`6`、`5`
> 比較：`4 < 6`、`6 < 5`
>
> 

由於要儲存兩者比賽的結果，這裡我們要調整一下最大值的求法

        private static final int[] tournament = new int[] {3, 1, 4, 1, 5, 9, 2, 6};

        public int[] findMaxAndSecond() {

            int len = tournament.length;

            // 贏家列表 (包含了之後的比賽所需的空間)
            int[] winner = new int[len - 1];
            // 輸家列表 (包含了之後的比賽所需的空間)
            int[] loser = new int[len - 1];

            int id = 0;

            // 首輪比賽
            // 使用 N/2 的比較
            for (int i = 0; i < tournament.length; i += 2) {

                int winnerTmp = tournament[i];
                int loserTmp = tournament[i + 1];

                if(loserTmp > winnerTmp) {
                    int tmp = winnerTmp;
                    winnerTmp = loserTmp;
                    loserTmp = tmp;
                }

                winner[id] = winnerTmp;
                loser[id] = loserTmp;

                id += 1;    // 會消耗一半的 Array，接著繼續 ...
            }

            // 儲存上一場贏家的 index 的列表
            int[] lastCompareResult = new int[len - 1];
            Arrays.fill(lastCompareResult, -1);    // 初始化為 -1

            int cIndex = 0;    // 贏家第二輪比賽的 index
            // 使用 N/2 的比較
            while (id < len - 1) {

                if(winner[cIndex] > winner[cIndex + 1]) {
                    winner[id] = winner[cIndex];
                    loser[id] = winner[cIndex + 1];

                    lastCompareResult[id] = cIndex;    // 將當前這輪的贏家 index 存起來
                } else {
                    winner[id] = winner[cIndex + 1];
                    loser[id] = winner[cIndex];

                    lastCompareResult[id] = cIndex + 1;
                }

                cIndex += 2;
                id += 1;
            }

            int largest = winner[cIndex];    // 最終求出的贏家結果
            
            // 第二名尚未比較完成
            int second = loser[cIndex];

            cIndex = lastCompareResult[cIndex];
            // 比較之前所有的贏家，最後才能得出第二名
            while (cIndex >= 0) {
                System.out.println("log compare: " + second + " < " + loser[cIndex] + "?");
                if(second < loser[cIndex]) {    // 比較次數為對數 log
                    second = loser[cIndex];
                }
                cIndex = lastCompareResult[cIndex];
            }

            return new int[] {largest, second};
        }

> 

該演算法的耗時重點為 `id`、`cIndex` 兩個屬性

`id` 就是 *N - 1*，而 `cIndex` 則是 *log(N) - 1*；

所以總耗時為 *N + log(N) - 2*

:::info
* 雖說使用了類似二元樹的演算法，但是該演算法的效能不好，**因為額外空間的消耗**
:::

## Appendix & FAQ

:::info
:::

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