算法学习总结(一)
目录
一、我们的征程
这里总结了自己学习算法的学习路线，按照颜色由浅及深共分为四个篇章
这个图就是关于算法的学习大纲、思路，最终学完之后，希望可以帮助大伙建立一个算法的知识体系，那么回过头大伙也可以看一下，我们学过哪些内容，他们可以解决对应的哪些问题，等等。
这张图左边浅颜色部分算是筑基，打基础，也是面试当中会经常问的部分，学完左边这部分之后，就可以进一步的去学习右边的部分，从而解决一些更复杂的问题。
- 分治和排序部分
如果大家平时有翻算法书或者算法课的话，你会发现，大家都会花很大心思去写排序相关的内容，为什么呢?
因为排序它本身包含了我们设计算法中最主要的操作，它是一个很简单的问题 ，但是抽象出来看的话，里面会有各种比较操作，通过比较得到我们最终想要的顺序，所以不要小看排序这个问题，虽然它本身是一个简单的问题，但是这里面有多种不同的设计方式，不同的实现思路；这里主要针对的是线性结构。
- 树和散列表
学完分治和排序掌握了这些比较基本的设计思想后，就可以学习新的数据结构了，这里我们引入了树和散列表；从树开始，数据结构会开始稍微复杂一点，包括后面的图等等；越是复杂的数据结构，它会加更多的限制，也就是我们在这样的数据结构上能够实现的算法能够解决的问题是有限的；
散列表就是哈希表，它使用起来是比较简单的，但是它的设计就稍微复杂点，它涉及到哈希探测的问题，也就是常说的哈希冲突问题；
- 图和算法优化
学会了树和散列表之后，我们就可以进一步的去解决更加复杂的问题，也会在力扣找一些经典的题去刷，总的来说这张图就是我们接下来关于算法的学习思路。
二、分治和排序
说到分治，这事我们从关于如何计算两个数相乘开始说起…
1、乘法问题
问题的定义：
输入: 2 个非负的数, x 与 y (各有 n 位)
输出: 两数乘积 x · y
比如：
我们在小学时是这样处理的，个位开始两两对齐，分别计算他们的乘积，最后求和得出两数相乘的结果。如果两个数的位数不是很大的话，这样做是可以的，但如果两个数的位数很大这样做就显得有点难为人了，比如下面的两个数
这样的两个数或者更大的两个数相乘，如果按照每一位分别与其它位相乘求和的话，可以分析它的时间复杂度是O( n 2 n^2 n2)。
我们能不能比O( n 2 n^2 n2)更快地计算n位整数相乘呢?
下面我们就来学习第一个算法设计范例----分治策略。
2、分治策略
分治策略的三个核心点:
-
分解(Devide) ：将一个大问题划分为一些子问题；
-
解决(Conquer) ：递归地解决这些子问题；
-
合并(Combine) ：将子问题的解组合成原问题的解 。
如图所示，
1、分治乘法
原问题是计算两个 n 位整数的乘积 ，我们如何划分子问题呢？下面通过一个例子来说明这件事，
上图描述的是将两个4位数相乘，通过提取最后变成了4个两位数相乘的子问题，通过这个例子我们可以映射出更一般的两个n位数相乘拆分成子问题的公式，即，
相应的我们可以写出对应的伪代码（我们通常用伪代码来描述一个算法的思路）：
那么这个算法的性能怎么样呢？我们尝试来求一下这个递归求解两个n位数相乘的时间复杂度。通过伪代码我们可以看到，每次递归调用都会将一个大问题拆分成四个子问题，每个子问题的大小是原问题的一半也就是 n 2 n \over 2 2n，直到位数为1的时候终止递归，那么相应的就可以画出该算法的递归树，如下所示
说明：
- Level 0层: 原问题为两个n位数相乘，也就是第0层问题个数为 4 0 4^0 40个大小为 n 2 0 n\over2^0 20n 的问题
- Level 1层: 每递归调用一次都会将原问题拆分成4个子问题，每个问题的大小为原问题的一半，即第一层问题个数为 4 1 4^1 41 个大小为 n 2 1 n\over 2^1 21n的问题
- Level t层: 可以看到规律，第t层问题的个数为 4 t 4^t 4t 个大小为 n 2 t n\over 2^t 2tn 的问题
- Level log 2 n \log_2n log2n 层 : 最后一层问题的个数为 4 log 2 n = n l o g 2 4 = n 2 4^ {\log_2n} =n^{log_24}=n^2 4log2n=nlog24=n2个大小为 n 2 log 2 n = n n log 2 2 = 1 {n \over 2^{\log_2n}}={n \over n^{\log_22}}=1 2log2nn=nlog22n=1的问题
- 最后把各层的处理次数也就是问题的个数加起来，忽略掉常熟、系数、低阶最终可得该算法的时间复杂度为O( n 2 n^2 n2)。
思考：最后一层为什么是 log 2 n \log_2n log2n层呢？
因为问题最初大小为n，每次递归调用都缩减为原问题的一半，也就是每一层都用n除以2，最后一层就相当于是求n除了几次2最终变成1，变相的等于求2的几次幂等于n，所以最后一层就是用 log 2 n \log_2n log2n来表示。
折腾了半天，时间复杂度还是 O ( n 2 ) O(n^2) O(n2)级的，看起来分治策略好像没什么用啊？继续往下看。
2、Karatsuba 乘法
Karatsuba says no!!!，分治乘法是可以优化滴，速度是可以提升滴！那他是如何优化的呢？请看图
为了得到这三个值，之前的分治算法计算了4项，也就是递归调用了4次最终得到 ac, ad, bc, bd的值，Karatsuba发现这里面ad+bc这项是不用分别调用ad和bc的，具体的做法如下：
- ac，bd依然使用递归求解
- ad+bc=(a+b)(c+d)-ac-bd，所以可以通过一次递归调用得到(a+b)(c+d)的值然后再分别减去ac和bd，ac和bd经过递归调用是已知的
所以经过优化之后，只需要三次递归调用就可以得到ac、ad+bc、bd的值，也就是每次递归调用将原问题拆分成3个子问题去解决，相应的递归锁就可以画出这样，
说明：
- Level 0层: 原问题为两个n位数相乘，也就是第0层问题个数为 3 0 3^0 30个大小为 n 2 0 n\over2^0 20n 的问题
- Level 1层: 每递归调用一次都会将原问题拆分成3个子问题，每个问题的大小为原问题的一半，即第一层问题个数为 3 1 3^1 31 个大小为 n 2 1 n\over 2^1 21n的问题
- Level t层 : 可以看到规律，第t层问题的个数为 3 t 3^t 3t 个大小为 n 2 t n\over 2^t 2tn 的问题
- Level log 2 n \log_2n log2n层 : 最后一层问题的个数为 3 log 2 n = n l o g 2 3 ≈ n 1.6 3^ {\log_2n} =n^{log_23} \approx n^{1.6} 3log2n=nlog23≈n1.6个大小为 n 2 log 2 n = n n log 2 2 = 1 {n \over 2^{\log_2n}}={n \over n^{\log_22}}=1 2log2nn=nlog22n=1的问题
- 最后把各层的处理次数也就是问题的个数加起来，忽略掉常熟、系数、低阶最终可得该算法的时间复杂度为O( n 1.6 n^{1.6} n1.6)。
类似的，还可以优化的更快，比如
3、排序
1、插入排序
插入排序，它的工作方式就像我们抓扑克牌一样。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插人左手中正确的位置。为了找到牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，拿在左手上的牌总是排序好的，如图2-1所示，
伪代码实现：
//A[3,2,6,8,1,5,4,7]--->[1,2,3,4,5,6,7,8]
InsertionSort(A):
for i in range(1, len(A)): //下标i表示正被插入到手中的当前牌,从1开始
cur_value = A[i]
j = i - 1
while j >= 0 and A[j] > cur_value:
A[j+1] = A[j]
j -= 1
A[j+1] = cur_value
思想：
-
外层循环 i 遍历数组中的元素，内层循环 j 实现排序功能，每次都把拿到的元素放到合适的位置上去；
-
每次与当前拿到元素的前一个元素进行比较，如果当前元素小于前一个元素，则把前一个元素向后移动，留出空位；然后继续比较，直到前一个元素不大于当前元素退出内层循环；
-
把当前元素的值插入到j+1的位置上去。
Java代码实现快速插入：
/**
* 快速插入排序，升序排列
*/
public class QuickInsert {
static void quickInsert(int []nums){
for (int i = 1; i <nums.length ; i++) {
int curVal=nums[i];
int j=i-1;
while(j>=0 && nums[j]>curVal){ //如果要降序排列，则直接改成nums[j]<curVal
nums[j+1]=nums[j];
j--;
}
nums[j+1]=curVal;
}
}
public static void main(String[] args) {
int nums[]={3,2,6,8,1,5,4,7};
// int nums[]={3,2,6,8,1,5,4,7,9,1};
// int nums[]={1,2,3,4,5,6};
quickInsert(nums);
for (int i = 0; i <nums.length ; i++) {
System.out.print(nums[i]);
}
}
}
插入排序的效率
通常使用大O记号来体现算法的时间复杂度，也就是通过统计语句执行的次数来估算方法的运行时间，这种表示方法描述的是运行时间的渐进上界，也就是最坏情况下运行方法需要的时间。
插入排序最坏情况下的运行时间：
InsertionSort(A):
for i in range(1, len(A)):
cur_value = A[i] //n次
j = i - 1 //n次
while j >= 0 and A[j] > cur_value: //n次
A[j+1] = A[j] //n^2次
j -= 1 //n^2次
A[j+1] = cur_value //n次
通过分析可知，插入排序的执行总次数为 4 n + 2 n 2 4n+2n^2 4n+2n2 次，根据大O的特性忽略掉系数、常熟、低阶，最终为 O ( n 2 ) O(n^2) O(n2)。
很显然 O ( n 2 ) O(n^2) O(n2)不是一个特别好的运行时间，那么问题来了，有没有更优的办法呢？
2、归并排序
我们刚介绍了分治策略，那我们就可以根据分治的思想来解决这个问题，操作如下:
- 分解，将待排序的n个元素的序列分解成两个长度为 n 2 n \over 2 2n的子序列;
- 解决，递归地调用自己排序两个子序列;
- 合并，合并两个已排序的子序列以产生最终排序的结果。
过程演示：
分解
解决&合并
伪代码实现：
MERGESORT(A):
n = len(A) //数组长度
if n <= 1: //数组长度=1的时候，开始返回合并
return A
L = MERGESORT(A[0:n/2])
R = MERGESORT(A[n/2:n])
return MERGE(L,R)
MERGE(L,R):
result = length n array
i = 0, j = 0
for k in [0,...,n-1]:
if L[i] < R[j]:
result[k] = L[i]
i += 1
else:
result[k] = R[j]
j += 1
return result
Java代码实现归并排序：
class Solution {
public int [] mergeSort(int []A){
if(A.length <= 1){ //终止条件
return A;
}
int []L; //左子数组
int []R; //右子数组
L=mergeSort(Arrays.copyOfRange(A, 0, A.length/2));//递归调用自己得到左子数组，每次传入数组A[0~n/2)包头不包尾
R=mergeSort(Arrays.copyOfRange(A, A.length/2,A.length ));//递归调用自己得到右子数组
return merge(L,R); //返回合并后的数组
}
public int [] merge(int []L,int []R){//合并&排序
int n=L.length+R.length;
int []result=new int[n];//封装合并左右子数组的数组
int i=0,j=0,k=0; //i遍历左子数组，j遍历右子数组，k对应结果result数组
//第一次while是左右子数组均不为空的情况，当不满足条件退出循环后，
//左或右子数组有可能还有元素没有添加到result数组中，所以需要额外再单独判断遍历
while(i<L.length&&j<R.length){
if( L[i]<R[j]){
result[k++]=L[i++];
}else {
result[k++]=R[j++];
}
}
//判断左子数组是否还有元素没取出来
while(i<L.length){
result[k++]=L[i++];
}
//判断右子数组是否还有元素没取出来
while(j<R.length){
result[k++]=R[j++];
}
return result;
}
public int[] sortArray(int[] nums) {
return mergeSort(nums);
}
public static void main(String[] args) {
int nums[]={3,2,6,8,1,5,4,7,9,10,11,12,13};
System.out.println(Arrays.toString(new MergeSort().mergeSort(nums)));
}
}
//Arrays.copyOfRange()方法测试
public static void main(String[] args) {
int[] src = new int[]{1, 2, 3, 4, 5};
int newArray[] = Arrays.copyOfRange(src, 0, src.length/2);
int newArray2[] = Arrays.copyOfRange(src, src.length/2,src.length );
for (int i : newArray) {
System.out.print(i);
}
System.out.println();
for (int i : newArray2) {
System.out.print(i);
}
System.out.println();
for (int i : src) {
System.out.print(i);
}
}
打印结果：
12
345
12345
归并排序的效率
归并排序是由递归实现的，关于递归算法的时间复杂度我们可以通过画递归树归纳总结得出，归并排序的递归树如图所示
通过归纳可知每一层总操作次数=子问题个数 X 子问题大小 X C =n，总共有 l o g 2 n log_2n log2n + 1 层, 每一层的操作次数为 n ⇒ 总计操作数也就是时间复杂度为 O(n log n)，所以归并排序的运行时间为 O(n log n)。
三、递归式与主定理
1、递归式
前面涉及到求递归算法的时间复杂度我们总是需要画递归树，归纳总结得出，每次这样感觉好麻烦，有没有更便捷的方式呢？
先回顾下刚刚画的归并排序的递归树，长成这个样子
整棵树我们可以将它一分为二，所以整棵树的总操作次数就可以归类为左子树+右子树+递归调用以外产生的操作次数，如图所示
如果整棵树操作时间为T(n)的话，那么左子树操作时间=右子树操作时间=T( n 2 n\over2 2n)，相应的我们可以写出表达式来描述该递归树的表达式:
T(n)=T( n 2 n\over2 2n)+T( n 2 n\over2 2n)+O(n)，因为子问题规模相同，所以也可以写成2 · T( n 2 n\over2 2n),整理后可得T(n)=2*T( n 2 n\over2 2n)+O(n)。
可以看到上式的定义是递归的，也就是要求T(n)需要先求T( n 2 n\over2 2n)，要求T( n 2 n\over2 2n)需要先求T( n 4 n\over4 4n)…依次类推，直到求到T(1)为止，所以我们称这样的式子为递归式，通过递归式来描述递归算法的运行时间。
可是，递归式和时间复杂度之间有什么关系呢？我们继续往下推！
通过推到归并排序的递归式，相应的我们可以求出分治乘法、karatsuba乘法的递归式，如图所示
观察递归式与它们对应的时间复杂度，这里似乎有些规律可循？
2、主定理
下面我们开始介绍一种求解大部分递归式时间复杂度的方法——主定理! 注意我这里的用词，是大部分，说明也会有一些主定理不适用的情况存在。
定义：
其中a、b、d含义如下：
- a: 表示子问题个数 (分支数量)，a大于等于1 是因为如果a=0那就表示递归式中T(n/b)这一项就不存在了，如果它不存在，则当前式子就不是表达递归的含义，所以a要大于等于1；
- b: 输入大小的缩小系数 (子问题的规模相比于原问题规模的缩小程度)，b要大于1是因为每次递归都将原问题拆分成子问题，如果等于1说明问题的规模没有发生变化，所以b要大于1；
- d: 需要 O( n d n^d nd) 次操作来创建子问题 + 合并子问题的解
还是有点模糊，那具体应该怎么用呢？看例子，
所以只需要根据将递归式中的a、b、d提取出来之后，然后比较a和 b d b^d bd之间的关系，往主定理里面带，根据比较的关系就可以得出对应的时间复杂度。
思考：a和 b d b^d bd之间的关系（=,>,<）有什么含义呢？
- 当a= b d b^d bd时，说明每一层的计算量相同，比如归并排序；
- 当a> b d b^d bd时，说明最下层比较重要，每层的计算量递增，会有越来越多的分支，最下层决定了整棵树的时间复杂度，比如分治乘法和karatsuba乘法；
- 当a< b d b^d bd时，那就是和大于的情况相反，也就是最上层比较重要，每层问题的计算量递减，目前我们还没有提到这种关系的算法，后面会接触到，比如QuickSelect。
验证主定理的结论
我们将递归式抽象为一般递归式，T(n) = a · T(n/b) + O( n d n^d nd) ⇒ T(n) = a · T(n/b) + c · n d n^d nd
根据递归式，通过填表方式，求出该递归式的总操作次数
将每一层操作总次数相加可得
所以我们就把a和 b d b^d bd之间的三种关系（=,>,<）分别带入这个式子里来验证对应的时间复杂度是否正确：
- 验证a= b d b^d bd的情况，时间复杂度为O( n d l o g n n^d logn ndlogn)
- 验证a< b d b^d bd的情况，时间复杂度为O( n d n^d nd)
- 验证a> b d b^d bd的情况，时间复杂度为O( n l o g b a n^{log_ba} nlogba)
推到过程：
至此我们就验证了主定理所有的情况，以后再求递归式的时间复杂度就可以套用主定理了，而不用每次都画递归树填表归纳总结那么麻烦了！
学习过程中难免会有理解偏差的地方，如果各位发现哪里有问题，及时评论，感激不尽！
每日一皮
同事骑的共享电动车回家，上了快速公路之后，由于超出骑行范围，车子自动断电了，推出快速路，最后为此还被罚了20块钱违规停车的钱，哈哈哈哈哈