時間複雜度和空間複雜度

1、概述

​ 演演算法就是解決一個問題的方法，同一個問題使用不同的演演算法得到相同的結果，但是所消耗的資源是不等的，這就意味著我們需要從眾多的演演算法中選出最優的那個演演算法。這個時候我們就不得不考慮這個演演算法的效率，而如何去評判或者判斷一個演演算法的好壞，一個演演算法的效率如何，那就需要用到這兩個指標：時間複雜性(消耗的時間)和空間複雜性(消耗的記憶體)。

2、時間複雜度

​ 定義：時間複雜度(Time complexity)，個演演算法語句總的執行次數是關於問題規模N的某個函數，它定性描述該演演算法的執行時間。時間複雜度常用大O符號表示

​ 統計方式：我們知道了什麼是時間複雜度，那麼我們怎麼去計算呢？當然也有兩種方式：一種是事後統計，演演算法寫好之後統計演演算法的執行時間，當然如果一個演演算法很劣質，那麼我們可能就需要推倒重來；另外一種就是事前分析，即在演演算法編寫之前我們先分析其執行的時間複雜度，從而判斷演演算法優劣

​ 複雜度的計算：演演算法的執行時長我們可以理解為所有簡單語句和每個簡單語句執行的時長。賦值、比較、移動、判斷、列印、一次資料庫的操作等等我們都可以理解成是一個簡單語句，從而：時間複雜度 = 簡單操作的次數 * 一個簡單操作的時間。一般一個簡單語句的執行時長跟我們的計算機的硬體效能有關，但是硬體效能卻與我們的演演算法質量無關，所以我們把每次簡單語句的執行時間相同都是單位1，那麼我們的時間複雜度就只與我們簡單操作的次數相關。

​ 例：有這樣一個需求，給出10個數位，6,8,3,2,16,7,9,13,4,17。得知其中兩個數位之和得26，找出這兩個資料分別是幾？

public class Test {
		// 定義所有數位的陣列
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定義兩數之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一個for迴圈得到第一個加數
        for (int i = 0; i < arr.length; i++) {
        		// 第二個for迴圈得到第二個加數，注意為了避免6+8 8+6這種重複，所以我們第二個加數直接把之前用過的數位去掉，節省一定迴圈次數
            for (int j = 0; j < arr.length; j++) {
            		// 拿著兩個加數相加看得到的是否等於最終結果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 兩數之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}

​ 分析：我們最終要執行的就是裡面的一個判斷，在這個裡面我們總共執行了多少次呢？外面迴圈是10次，裡面一個迴圈每次也執行10次，如果按照最差結果，那麼要執行10的2次方一百次。如果我們有100個數，那麼就是100的2次方就是一萬次，如果再往上增加恐怕這個數值的恐怖程度會超出我們的想想吧,如此來說這個演演算法的時間複雜度是與陣列長度有關係的假設我們陣列長度是N，那麼我們的計算次數就是N的2次方，事件複雜度與執行次數成正比，那麼時間複雜度記為：O(n^2)

​ 降低時間複雜度： 我們感覺上面那種方式時間複雜度太高了，那麼有什麼辦法降低呢，看下面這種方式

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定義一個map存放能夠得到目標數值的兩個加數，key是當前值為了能得到最終值所需要的另一個加數，value就是我們當前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判斷這個當前數值是否是之前數所需要的數值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 兩數之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }

​ 分析：經過這次改造，看我們還需要執行多少次呢？原來需要兩個迴圈，現在我們需要一個迴圈，那麼需要執行N次能得到最終的結果。那麼我們的時間複雜度為：O(n)

​ 如果我們的一個演演算法，從頭到位順序執行不存在迴圈等條件，每行語句都執行一次或者固定次數，那麼我們的時間複雜度就是O(1),那麼我們總結一下，什麼是時間複雜度，就是我們演演算法執行需要的時間，而怎麼計算這個需要考慮我們演演算法中各個影響因素，以最重要因素為主去算我們的最終複雜度

3、空間複雜度

​ 定義：空間複雜度(Space Complexity)是對一個演演算法在執行過程中臨時佔用儲存空間大小的量度，記做S(n)=O(f(n))

​ 一個演演算法執行時所佔用的空間一般分兩部分，一個是固定的，指程式碼部分，就是我們的程式碼的多少，定義常數的，簡單變數的多少；另一部分就是在我們程式碼執行中所產生的臨時變數所佔用的空間，這部分空間是不確定的，而我們所說的空間複雜度說的就是這部分空間的的佔用情況

​ 例: 我們延用上面的兩個案例來分析一下他們的空間複雜度

​ case1

public class Test {
		// 定義所有數位的陣列
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定義兩數之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一個for迴圈得到第一個加數
        for (int i = 0; i < arr.length; i++) {
        		// 第二個for迴圈得到第二個加數，注意為了避免6+8 8+6這種重複，所以我們第二個加數直接把之前用過的數位去掉，節省一定迴圈次數
            for (int j = 0; j < arr.length; j++) {
            		// 拿著兩個加數相加看得到的是否等於最終結果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 兩數之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}

​ 分析：在這個案例裡面在執行時我們沒有定義任何變數，所以無論我們的陣列元素變成多少，我們所佔用的記憶體空間是固定的，那麼我們的空間複雜度就是O(1)

​ case2：

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定義一個map存放能夠得到目標數值的兩個加數，key是當前值為了能得到最終值所需要的另一個加數，value就是我們當前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判斷這個當前數值是否是之前數所需要的數值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 兩數之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }

​ 分析：在case2中看到我們定義了一個map來儲存陣列元素，當我們開始執行時，map建立出來，隨著我們陣列元素的增多，我們map中所需要的空間也會不斷增多，這個時候我們的空間複雜度就變成了：O(n)，n就是我們陣列的長度

4、空間與時間

​ 我們經常聽到的一句話，利用空間換時間，利用時間換空間，其實在這裡我們已經能深刻的體會出來了。這句話聽著有點魚與熊掌不可兼得的味道，但是目前來說大部分情況就是這個樣子，有失有得，你總要付出一點代價方能得到一些。但是在我們目前的環境中這種選擇似乎沒有之前那麼艱難，最開始的時候受資盤等的限制，一個程式的執行只有幾K或者幾百K，這個時候究竟是選擇時間還是空間就會成為一個糾結的問題，隨著計算機的發展，現在的磁碟記憶體等已經能夠得到大部分需求的滿足，所以在大部分情況下在選擇空間與時間的問題上，選擇時間的會偏多一點

不斷努力，共同成長

關注公眾號不迷路