目錄

一.演算法效率

二. 時間復雜度

1.時間復雜度的概念

2.大O的漸進表示方法

3.實體分析與計算

三.空間復雜度

1.空間復雜度的概念

2.實體分析與計算

四.寫在最后

一.演算法效率

演算法效率分析分為兩種：時間效率、空間效率，其中時間效率被稱為時間復雜度，空間效率被稱為空間復雜度，

時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額
外空間

由于早期計算機儲存容量很少，所以通常是浪費時間來換取空間，而隨著計算機的高速發展，計算機的存盤容量已經達到了很高水平，所以現在通常是浪費空間換取時間

二. 時間復雜度

1.時間復雜度的概念

在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，但是一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，全部演算法的上機測驗顯然是不現實的，于是才有了時間復雜度的分析方式：演算法中的基本操作的執行次數，是為演算法的時間復雜度，

有些演算法的時間復雜度存在最壞、最好和平均情況，一般來說，實際情況中，我們所求的時間復雜度指的是最壞情況

最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)

2.大O的漸進表示方法

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用的就是大O的漸進表示法

接下來我們看看推導大O階的基本原則

1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階

3.實體分析與計算

//計算bubbleSort的時間復雜度
void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }

該演算法最壞情況下執行了(N*(N-1))/2次，通過推導大O階方法可以得出其時間復雜度為O(N)

// 計算binarySearch的時間復雜度
    int binarySearch(int[] array, int value) {
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end-begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }

該演算法最壞情況下執行O(logN)次，時間復雜度為 O(logN)，ps：logN在演算法分析中表示是底數為2，對數為N，有些地方會寫成lgN，該演算法為二分查找，可以通過畫圖來借助理解，得出運算式為：N/2^X=1，X就是執行操作的次數

// 計算階乘遞回factorial的時間復雜度？
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;
    }

基本操作遞回了N次，時間復雜度為O(N)

// 計算斐波那契遞回fibonacci的時間復雜度
    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

基本操作遞回了2^N次，時間復雜度為O(2^N)

三.空間復雜度

1.空間復雜度的概念

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，而是算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法

2.實體分析與計算

// 計算bubbleSort的空間復雜度
    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }

該演算法使用了常數個額外空間，所以空間復雜度為 O(1)

// 計算fibonacci的空間復雜度
    int[] fibonacci(int n) {
        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

該演算法動態開辟了N個空間，空間復雜度為 O(N)

// 計算階乘遞回Factorial的時間復雜度
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1)*N;
    }

該演算法遞回呼叫了N次，開辟了N個堆疊幀，每個堆疊幀使用了常數個空間，空間復雜度為O(N)

四.寫在最后

由于期末專業課較多，加上自己自控力不足，導致斷更了一段時間，寒假決定洗心革面，把斷更的博文都補起來，博主在寫博客程序中可能出現一些錯誤，望大家斧正，以及由任何問題可以在評論區或者私信與博主交流，希望大家寒假能有所識訓，一起卷起來！