第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

章節(jié)導(dǎo)讀

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

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

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度描述的是算法執(zhí)行需要消耗的時(shí)間。同等條件下，消耗時(shí)間越少，算法性能越好。但是，算法執(zhí)行的確切時(shí)間無(wú)法直接測(cè)量，通常只有在實(shí)際運(yùn)行時(shí)才能知道。所以我們通過(guò)估算算法代碼的方法來(lái)得到算法的時(shí)間復(fù)雜度。

空間復(fù)雜度

空間復(fù)雜度描述的是算法在執(zhí)行過(guò)程中所消耗的存儲(chǔ)空間（內(nèi)存+外存）。同等條件下，消耗空間資源越少，算法性能越好。

大O符號(hào)

大O符號(hào)是用于描述函數(shù)漸近行為的數(shù)學(xué)符號(hào)，在分析算法效率的時(shí)候非常有用。

借用wikipedia上的一個(gè)例子，解決一個(gè)規(guī)模為n的問(wèn)題所花費(fèi)的時(shí)間可以表示為：T(n)=4n²+2n+1。當(dāng)n增大時(shí)，n²項(xiàng)將開(kāi)始占主導(dǎo)地位，而其他各項(xiàng)可以被忽略。比如當(dāng)n=500，4n²項(xiàng)是2n項(xiàng)的1000倍大，因此在大多數(shù)場(chǎng)合下，省略后者對(duì)表達(dá)式的值的影響將是可以忽略不計(jì)的。

長(zhǎng)遠(yuǎn)來(lái)看，如果我們與任一其他級(jí)的表達(dá)式比較，n²項(xiàng)的系數(shù)也是無(wú)關(guān)緊要的。例如：一個(gè)包含n²項(xiàng)的表達(dá)式，即使T(n)=1,000,000n²，假定U(n)=n³，一旦n增長(zhǎng)到大于1,000,000，后者就會(huì)一直超越前者。

案例：Two Sum

給出一個(gè)整數(shù)數(shù)組nums和一個(gè)target整數(shù)，返回兩個(gè)和為target的整數(shù)。

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

1.向面試官確認(rèn)輸入、輸出
通過(guò)詢(xún)問(wèn)面試官，我們可以知道：輸入是一個(gè)int類(lèi)型的數(shù)組和一個(gè)target；返回值是兩個(gè)下標(biāo)，并且以數(shù)組的形式返回；方法名沒(méi)有特殊要求。這樣一下我們就確定了函數(shù)的簽名

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

2.向面試官確認(rèn)輸入、輸出是否有特例

接下來(lái)我們要確認(rèn)一下輸入輸出的細(xì)節(jié)

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

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

假設(shè)面試官告訴我們：只需要寫(xiě)函數(shù)本身。輸入數(shù)組可能為空，但不會(huì)大到無(wú)法讀進(jìn)內(nèi)存。數(shù)字的范圍就是int類(lèi)型的范圍，可能有重復(fù)。對(duì)于不合法或者沒(méi)有正確答案的情況，請(qǐng)自行判斷。多個(gè)解法是，返回任意一個(gè)答案都可以。

得到了這些信息，我們可以先進(jìn)行防御性編程。

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.舉幾個(gè)例子

接下來(lái)，我們可以要求面試官舉幾個(gè)例子，或者自己提出幾個(gè)例子，來(lái)確保雙方對(duì)題目沒(méi)有異議。

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]

• 根據(jù)例子1、2，確定沒(méi)有正確解時(shí)返回空數(shù)組。
• 根據(jù)例子2，確定數(shù)字不可重復(fù)使用。
• 根據(jù)例子3、4，確定如果有多個(gè)合適的解，返回任意一個(gè)都可以。

4. 開(kāi)始解題

完成了之前的步驟，需要找到正確的思路。這道題有三種思路，我們需要一一分析判斷，找到合適的解法之后，和面試官進(jìn)行討論。得到面試官的允許之后，才可以開(kāi)始寫(xiě)代碼。（如果一上來(lái)就埋頭解題，即使做對(duì)了也不能拿到最高評(píng)價(jià)。）

解法1 Brute Force

沒(méi)有具體思路的時(shí)候，暴力破解法應(yīng)該是第一個(gè)想法。幾乎任何后續(xù)更高效的算法都是在暴力破解法的基礎(chǔ)上優(yōu)化而來(lái)的。即使無(wú)法優(yōu)化成功，一個(gè)可行解也好過(guò)一個(gè)高效但不可行的算法。

對(duì)于Two Sum這道題，最直觀的想法大概是找到所有可能的數(shù)字組合，挨個(gè)計(jì)算他們的和，返回第一個(gè)滿(mǎn)足條件的組合。這種解法并沒(méi)有什么技術(shù)含量，但是可以作為我們下一步優(yōu)化的基礎(chǔ)。

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]; // 確定第一個(gè)可能的數(shù)字
        for (int j = i + 1; j < nums.length; j++) { // O(N)
            int secondNum = nums[j]; // 確定第二個(gè)可能的數(shù)字
            if (firstNum + secondNum == target) {
                return new int[]{firstNum, secondNum};
            }
        }
    }
    return new int[0];
}

假設(shè)我們的輸入大小為N（即nums的長(zhǎng)度為N），for循環(huán)遍歷每個(gè)數(shù)字時(shí)，假設(shè)每訪(fǎng)問(wèn)一個(gè)數(shù)字需要消耗的1個(gè)單位的時(shí)間，那么對(duì)于長(zhǎng)度為N的數(shù)組，一共需要消耗N的時(shí)間。在計(jì)算機(jī)領(lǐng)域，我們使用大O記號(hào)來(lái)表示這種量化方法，將for循環(huán)的消耗記為O(N)。由于解法1中，我們使用了嵌套了兩重for循環(huán)，這說(shuō)明我們對(duì)于N個(gè)數(shù)字，每個(gè)數(shù)字除了消耗1個(gè)單位時(shí)間用于訪(fǎng)問(wèn)，還消耗了N個(gè)時(shí)間第二次遍歷數(shù)組，總體的時(shí)間消耗為O(N²).

解法2 使用HashSet

反思解法1的步驟，我們利用了兩重for循環(huán)。第一層for循環(huán)我們有不得不使用的理由：因?yàn)槲覀冎辽傩枰闅v每個(gè)數(shù)字。第二個(gè)for循環(huán)的目的是找到與firstNum相加等于target的數(shù)字，在這里我們又使用了for循環(huán)。如果有一種辦法能夠讓我們記住已經(jīng)見(jiàn)過(guò)的數(shù)字，并且在O(1)的時(shí)間內(nèi)檢查是否有數(shù)字與firstNum相加等于taget，那么就可以省下一個(gè)O(N)的for循環(huán)。

有一個(gè)已知的數(shù)據(jù)結(jié)構(gòu)可以解決這個(gè)問(wèn)題——Set。Set對(duì)應(yīng)數(shù)學(xué)意義上的集合，每個(gè)元素在集合中只出現(xiàn)一次，Set提供了add/remove/contains … 等API，并且非常高效消耗均為O(1)。

在遍歷數(shù)組的過(guò)程中，每遇到一個(gè)新的數(shù)字num，計(jì)算target - num的值并記為potentialMatch。檢查set中是否包含potentialMatch，如果包含說(shuō)明存在這么一組數(shù)字對(duì)，他們的和等于target；如果不包含，那么將當(dāng)前的num加入set，然后檢查下一個(gè)數(shù)字。

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];
}

這個(gè)方法利用了Set的特性：以O(shè)(1)的速度快速查詢(xún)?cè)厥欠翊嬖?。從而省去了一個(gè)for循環(huán)，將時(shí)間復(fù)雜度降到了O(N)。但是Set消耗了額外的空間，在最差的情況下，Set可能保存了每一個(gè)數(shù)字但依舊返回了空數(shù)組。所以，解法二消耗了O(N)的空間和O(N)的時(shí)間。

解法3 使用排序

解法2利用了O(N)的額外空間去記錄已經(jīng)訪(fǎng)問(wèn)過(guò)的數(shù)組。那么是否存在一種辦法可以不消耗額外的空間，同時(shí)提供高效地查詢(xún)。

當(dāng)然沒(méi)有這種好事?……

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

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

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所指向的數(shù)字就是我們要找的結(jié)果
            return new int[] {nums[left], nums[right]};
        } else if (sum < target) {
            // 如果sum小于target，那么將left向右移動(dòng)一位，讓下一個(gè)sum變大
            left++;
        } else if (sum > target) {
            // 如果sum大于target，那么將right向左移動(dòng)一位，讓下一個(gè)sum變小
            right--;
        }
    }
    return new int[0];
}

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

時(shí)間-空間的取舍

讓我們來(lái)回顧這三種解法：

• 解法1消耗了O(N²)的時(shí)間和O(1)的空間
• 解法2消耗了O(N)的時(shí)間和O(N)的空間
• 解法3消耗了O(NlogN)的時(shí)間和O(1)的空間

與解法1的暴力算法相比，解法2是用了空間換時(shí)間，增加了Set的消耗，減短了查詢(xún)的消耗。解法3則相反，用了時(shí)間換空間，通過(guò)原地排序，省去了Set。這兩類(lèi)操作統(tǒng)稱(chēng)space-time trade-off 空間-時(shí)間權(quán)衡。

通過(guò)對(duì)算法的復(fù)雜度分析，我們有了量化算法效率的方法。我們可以明確地指出，解法2比解法1更好，解法3比解法2消耗更少的內(nèi)存。

大多數(shù)情況下，算法的過(guò)程是基于對(duì)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的操作。因此分析算法復(fù)雜度也要求我們掌握常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。上表給出了常用數(shù)據(jù)結(jié)構(gòu)和操作的時(shí)間復(fù)雜度。記住這張表，能幫助我們更快的分析一個(gè)新算法的復(fù)雜度。

習(xí)題

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