共计 4789 个字符，预计需要花费 12 分钟才能阅读完成。
本文首发自「慕课网」，想理解更多 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
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 圈优质内容，分享干货常识，大家一起独特成长吧！
本文原创公布于慕课网，转载请注明出处，谢谢合作
