亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

章節導讀

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

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

時間復雜度

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

空間復雜度

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

大O符號

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

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

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

案例：Two Sum

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

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

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

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

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

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

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

有些問題即使題目中已經提到，最好還是再次向面試官確認。如果以上這些問題你沒有想到的話，那么說明思路僅限于做題，缺乏面試的溝通技巧?？梢远嗾倚』锇镸ock面試，注意多交流。

假設面試官告訴我們：只需要寫函數本身。輸入數組可能為空，但不會大到無法讀進內存。數字的范圍就是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，確定如果有多個合適的解，返回任意一個都可以。

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(N²).

解法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

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

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(N²)的時間和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消耗更少的內存。

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

習題

Two Sum有另一種版本不同于上文中的例題，要求返回的是數字的下標，與例題略有不同，非常適合作為習題