本文首發自「慕課網」，想了解更多IT乾貨內容，程式設計師圈內熱聞，歡迎關注！

作者| 慕課網精英講師 S09g

同一道問題可能有多種解決方案。自然地，我們會將多種方法進行比較。那麼怎麼樣才能知道是A方法好，還是B方法好？這時候我們就需要對算法的複雜度進行分析。

本篇文章我們先介紹兩個概念：時間複雜度與空間複雜度。並且用Two Sum作為案例，用時間空間複雜度分析Two Sum的三種解法

時間複雜度

時間複雜度描述的是算法執行需要消耗的時間。同等條件下，消耗時間越少，算法性能越好。但是，算法執行的確切時間無法直接測量，通常只有在實際運行時才能知道。所以我們通過估算算法代碼的方法來得到算法的時間複雜度。

空間複雜度

空間複雜度描述的是算法在執行過程中所消耗的存儲空間（內存+外存）。同等條件下，消耗空間資源越少，算法性能越好。

大O符號

大O符號是用於描述函數漸近行為的數學符號，在分析算法效率的時候非常有用。

借用wikipedia上的一個例子，解決一個規模為n的問題所花費的時間可以表示為：T(n)=4n2+2n+1。當n增大時，n2項將開始占主導地位，而其他各項可以被忽略。比如當n=500，4n2項是2n項的1000倍大，因此在大多數場合下，省略後者對表達式的值的影響將是可以忽略不計的。

長遠來看，如果我們與任一其他級的表達式比較，n2項的係數也是無關緊要的。例如：一個包含n2項的表達式，即使T(n)=1,000,000n2，假定U(n)=n3，一旦n增長到大於1,000,000，後者就會一直超越前者。

案例：Two Sum

給出一個整數數組nums和一個target整數，返回兩個和為target的整數。

假定我們正在面試，讓我們用面試的方法來分析一下這道題。

1.向面試官確認輸入、輸出
通過詢問面試官，我們可以知道：輸入是一個int類型的數組和一個target；返回值是兩個下標，並且以數組的形式返回；方法名沒有特殊要求。這樣一下我們就確定了函數的簽名

public int[] twosum(int[] nums, int target) {
  // Solution
}

2.向面試官確認輸入、輸出是否有特例

接下來我們要確認一下輸入輸出的細節

輸入是否可以為空？
輸入的數組範圍是正整數，還是任意範圍？
輸入數組會不會特別大，甚至無法載入內存，比如300GB的數據量？
如果輸入不合法或者沒有正確答案，我們已經返回空數組還是拋出異常？
輸入的數組中有重複麼？如果沒有重複，可以同一個數字用兩次麼？
如果有多個解，那麼返回第一個，還是所有解？
你希望答案寫成class，還是只提供方法本身即可？
……

有些問題即使題目中已經提到，最好還是再次向面試官確認。如果以上這些問題你沒有想到的話，那麼說明思路僅限於做題，缺乏面試的溝通技巧。可以多找小夥伴Mock面試，注意多交流。

假設面試官告訴我們：只需要寫函數本身。輸入數組可能為空，但不會大到無法讀進內存。數字的範圍就是int類型的範圍，可能有重複。對於不合法或者沒有正確答案的情況，請自行判斷。多個解法是，返回任意一個答案都可以。

得到了這些信息，我們可以先進行防禦性編程。

public int[] twoSum(int[] nums, int target) {
  if (nums == null || nums.length < 2) {
    return new int[0];
  }
  
  // TODO: solution here
  
  return new int[0];
}

3.舉幾個例子

接下來，我們可以要求面試官舉幾個例子，或者自己提出幾個例子，來確保雙方對題目沒有異議。

Example 1:
Input: nums = [], target = 0
Output: []

Example 2:
Input: nums = [2], target = 4
Output: []

Example 3:
Input: nums = [2, 3, 4, 2], target = 6
Output: [2, 4] or [4, 2]

Example 4:
Input: nums = [2, 7, 11, -2], target = 9
Output: [2, 7] or [7, 2] or [11, -2] or [-2, 11]

根據例子1、2，確定沒有正確解時返回空數組。
根據例子2，確定數字不可重複使用。
根據例子3、4，確定如果有多個合適的解，返回任意一個都可以。

開始解題

完成了之前的步驟，需要找到正確的思路。這道題有三種思路，我們需要一一分析判斷，找到合適的解法之後，和面試官進行討論。得到面試官的允許之後，才可以開始寫代碼。（如果一上來就埋頭解題，即使做對了也不能拿到最高評價。）

解法1 Brute Force

沒有具體思路的時候，暴力破解法應該是第一個想法。幾乎任何後續更高效的算法都是在暴力破解法的基礎上優化而來的。即使無法優化成功，一個可行解也好過一個高效但不可行的算法。

對於Two Sum這道題，最直觀的想法大概是找到所有可能的數字組合，挨個計算他們的和，返回第一個滿足條件的組合。這種解法並沒有什麼技術含量，但是可以作為我們下一步優化的基礎。

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return new int[0];
    }

    for (int i = 0; i < nums.length; i++) { // O(N)
        int firstNum = nums[i]; // 確定第一個可能的數字
        for (int j = i + 1; j < nums.length; j++) { // O(N)
            int secondNum = nums[j]; // 確定第二個可能的數字
            if (firstNum + secondNum == target) {
                return new int[]{firstNum, secondNum};
            }
        }
    }
    return new int[0];
}

假設我們的輸入大小為N（即nums的長度為N），for循環遍歷每個數字時，假設每訪問一個數字需要消耗的1個單位的時間，那麼對於長度為N的數組，一共需要消耗N的時間。在計算機領域，我們使用大O記號來表示這種量化方法，將for循環的消耗記為O(N)。由於解法1中，我們使用了嵌套了兩重for循環，這說明我們對於N個數字，每個數字除了消耗1個單位時間用於訪問，還消耗了N個時間第二次遍歷數組，總體的時間消耗為O(N2).

解法2 使用hashSet

反思解法1的步驟，我們利用了兩重for循環。第一層for循環我們有不得不使用的理由：因為我們至少需要遍歷每個數字。第二個for循環的目的是找到與firstNum相加等於target的數字，在這裡我們又使用了for循環。如果有一種辦法能夠讓我們記住已經見過的數字，並且在O(1)的時間內檢查是否有數字與firstNum相加等於taget，那麼就可以省下一個O(N)的for循環。

有一個已知的數據結構可以解決這個問題——Set。Set對應數學意義上的集合，每個元素在集合中只出現一次，Set提供了add/remove/contains … 等API，並且非常高效消耗均為O(1)。

在遍歷數組的過程中，每遇到一個新的數字num，計算target - num的值並記為potentialMatch。檢查set中是否包含potentialMatch，如果包含說明存在這麼一組數字對，他們的和等於target；如果不包含，那麼將當前的num加入set，然後檢查下一個數字。

public int[] towSum(int[] nums, int target) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) { // O(N)
        int potentialMatch = target - num;
        if (set.contains(potentialMatch)) { // O(1)
            return new int[]{potentialMatch, num};
        } else {
            set.add(num); // 空間消耗增加O(1)
        }
    }
    return new int[0];
}

這個方法利用了Set的特性：以O(1)的速度快速查詢元素是否存在。從而省去了一個for循環，將時間複雜度降到了O(N)。但是Set消耗了額外的空間，在最差的情況下，Set可能保存了每一個數字但依舊返回了空數組。所以，解法二消耗了O(N)的空間和O(N)的時間。

解法3 使用排序

解法2利用了O(N)的額外空間去記錄已經訪問過的數組。那麼是否存在一種辦法可以不消耗額外的空間，同時提供高效地查詢。

當然沒有這種好事?……

除非我們做一步預處理：將輸入的數組排序處理。比如下圖的例子：nums = [2, 4, 9, 7, 1], target = 6

先將原數組進行排序(這裡可以使用程式語言自帶的排序方法)
創建left、right兩根指針。left指向第一位，right指向最後一位
只要left和right不重合，循環比較left、right指向的兩個數字的和sum：如果sum等於target，那麼left、right所指向的數字就是我們要找的結果如果sum大於target，那麼將right向左移動一位，讓下一個sum變小如果sum小於target，那麼將left向右移動一位，讓下一個sum變大
當循環結束，依舊沒有答案，說明沒有正確解

public int[] twoSum(int[] nums, int target) {
    Arrays.sort(nums); // O(NlogN)
    int left = 0;
    int right = nums.length - 1;
    while (left < right) { // O(N)
        int sum = nums[left] + nums[right];
        if (sum == target) { 
            // 如果sum等於target，那麼left、right所指向的數字就是我們要找的結果
            return new int[] {nums[left], nums[right]};
        } else if (sum < target) {
            // 如果sum小於target，那麼將left向右移動一位，讓下一個sum變大
            left++;
        } else if (sum > target) {
            // 如果sum大於target，那麼將right向左移動一位，讓下一個sum變小
            right--;
        }
    }
    return new int[0];
}

這個算法的優勢在於每次只會讓較大的值減小、或者較小的值增大，得到的sum是連續的。如果存在正確的解，就一定可以找到對應的left和right。left、right的單調移動，每次會排除一部分錯誤答案，減小搜索空間，而且保證了數組中每個數字僅被訪問一次，消耗是O(N)的。但是在預處理的時候使用了排序，所以會有O(NlogN)的時間消耗。總體上消耗了O(NlogN)的時間和O(1)的空間。缺點是改變了原數組的元素位置。

時間-空間的取捨

讓我們來回顧這三種解法：

解法1消耗了O(N2)的時間和O(1)的空間
解法2消耗了O(N)的時間和O(N)的空間
解法3消耗了O(NlogN)的時間和O(1)的空間

與解法1的暴力算法相比，解法2是用了空間換時間，增加了Set的消耗，減短了查詢的消耗。解法3則相反，用了時間換空間，通過原地排序，省去了Set。這兩類操作統稱space-time trade-off 空間-時間權衡。

通過對算法的複雜度分析，我們有了量化算法效率的方法。我們可以明確地指出，解法2比解法1更好，解法3比解法2消耗更少的內存。

數據結構	關鍵信息
array	通過下標訪問O(1)，查詢O(N)，插入O(N)，刪除O(N)
string	在內存中的形式與array等價
linked list	通過下標訪問O(N)，查詢O(N)，插入O(1)，刪除O(1)
stack	last-in first-out，在內存中的形式等價於linked list
queue	first-in first-out，在內存中的形式等價於linked list
heap	查詢極值O(1)，插入O(logN)，刪除極值O(N)
hash table	插入、刪除、查詢O(1)
binary search tree	插入、刪除、查詢、找最大最小值、訪問前驅結點、訪問後繼節點均為O(1)

大多數情況下，算法的過程是基於對基礎數據結構的操作。因此分析算法複雜度也要求我們掌握常見的數據結構。上表給出了常用數據結構和操作的時間複雜度。記住這張表，能幫助我們更快的分析一個新算法的複雜度。

歡迎關注「慕課網」，發現更多IT圈優質內容，分享乾貨知識，幫助你成為更好的程式設計師！

一定要會的算法複雜度分析，簡直yyds！