本文首发自「慕课网」，想理解更多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 = 0Output: []
Example 2:Input: nums = [2], target = 4Output: []
Example 3:Input: nums = [2, 3, 4, 2], target = 6Output: [2, 4] or [4, 2]
Example 4:Input: nums = [2, 7, 11, -2], target = 9Output: [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

1.先将原数组进行排序(这里能够应用编程语言自带的排序办法)
2.创立left、right两根指针。left指向第一位，right指向最初一位
3.只有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圈优质内容，分享干货常识，大家一起独特成长吧！
本文原创公布于慕课网 ，转载请注明出处，谢谢合作