本文首發自「慕課網」，想了解更多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 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消耗更少的記憶體。

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

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