最近，把极客时间上的算法看完之后，基本也就停留在看完的阶段了。今天的主要任务是把这部分东西，再总结再看一遍。尤其是排序算法，然后把一些结论性的东西总结一下，方便之后复习。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。
数据结构
数组
数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。
链表
和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。
应用：LRU 缓存淘汰算法。
栈
栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现（顺序栈），也可以通过链表来实现（链式栈）。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。可以利用动态扩容的数组实现支持动态扩容的顺序栈。
应用：浏览器前进和后退功能；函数调用；表达式求值，括号匹配。
队列
队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。
在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，就需要像环一样的循环队列。基于数组实现的，受限于空间大小，不能像链表那样无限延伸。
对于循环队列，队列为空时，判断条件为 head==tail；当队列满时，(tail+1)%n=head，也就是说，tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
不同于栈需要一个栈顶指针，因为涉及到出队和入队操作，所以队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾（最后一个元素的下一个空白位置）。
阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。
散列表
散列表（Hash Table），也称为“哈希表”或者“hash 表”。散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。具体过程为通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法，开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。
二叉树
每个节点最多有两个子节点，则为二叉树。
满二叉树：
- 叶子节点全部都在底层
- 除了叶子节点之外，每个节点都有左右两个子节点
完全二叉树：
- 叶子节点都在最底下两层
- 最后一层的叶子节点都靠左排列；
- 除了最后一层，其他层的节点个数都要达到最大
二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。
二叉查找树（Binary Search Tree）也叫做二叉搜索树。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)。
平衡二叉查找树是红黑树，可以避免二叉查找树的时间复杂度退化。
排序算法
排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
原地排序算法：特指空间复杂度是 O(1) 的排序算法。
选择排序最好情况下的复杂度也是$O(n^2)$，并且不是稳定的。
后面三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。所以时间复杂度低，但是对数据要求比较高。
编程技巧
递归
递归是一种应用非常广泛的算法（或者编程技巧）。递归分为两个步骤：去的过程叫“递”，回来的过程叫“归”。
当问题满足如下三个条件时，则适合使用递归解决：
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件。另外，还需要注意的是，要通过几个边界值例子，看终止条件是否足够。
写递归代码有两个最关键的步骤：
- 写出递推公式
- 找到终止条件
理解递归代码需要把握住如下几点：
- 如果试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区
- 如果一个问题 A 可以分解为若干子问题 B、C、D，可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，理解起来就简单多了。
- 因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所有的递归代码都可以改为迭代循环的非递归写法。
算法
贪心算法
贪心算法使用的场景非常有限。贪心算法解决问题正确性虽然显而易见，但并不好证明，只需要举几个例子说明即可。
贪心算法解决问题的步骤如下：
- 当看到这类问题：针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。首先要联想到贪心算法。
- 尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
- 举几个例子看贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
分治算法
分治算法的核心思想是分而治之。定义类似于递归，区别在于分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。
分层算法的递归实现中，每一层递归都会涉及到如下三个操作：
- 分解：将原问题分解成一系列子问题；
- 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
- 合并：将子问题的结果合并成原问题。
分治算法能解决的问题，一般要满足如下几个条件：
- 原问题与分解成的小问题具有相同的模式；
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
- 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
- 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
回溯算法
回溯算法大多应用在“搜索”这类问题上，即在一组可能的解中，搜索满足期望的解。
回溯的处理思想类似于枚举搜索，枚举所有的解，找到满足期望的解。为避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段都会面对一个岔路口，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。实际例子为0-1背包问题以及八皇后问题。
动态规划
大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是动态规划的空间复杂度也提高了。
适用问题
这里就涉及到了“一个模型三个特征”理论。
一个模型定义为“多阶段决策最优解模型”。一般使用动态规划解决最优问题。解决问题的过程，需要经历多个决策阶段，每个决策阶段都对应着一组状态。需要寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
”三个特征“分别为最优子结构、无后效性和重复子问题。下面对这三个概念详细解释一下。
- 最优子结构：可以通过子问题的最优解，推导出问题的最优解。结合动态规划问题，就是后面阶段的状态可以通过前面阶段的状态推导出来
- 无后效性：第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
- 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
解决思路
能用动态规划解决的问题，都可以用回溯算法的暴力搜索解决。具体过程如下：
- 先用回溯算法解决，定义状态，每个状态表示一个节点，然后画出对应的递归树。
- 从递归树中观察是否存在重复子问题，以及如何产生的，借此寻找规律，看能否用动态规划解决。
- 找到重复子问题后，一般有两个解决思路。一种是回溯加“备忘录”的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。
所谓状态转移表法：先画出一个状态表。状态表一般都是二维的，可以想象成一个二维数组。其中，每个状态包含三个变量，行、列、数组值。然后，根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻译成代码，就是动态规划代码了。
但是若问题的状态比较复杂，需要很多变量表示，那对应的状态表就是高维的，而不是二维的。这个时候就不适合使用状态转移表法了。此时就需要借助于状态转移方程法了。
状态转移方程法有点类似递归的解题思路。需要分析某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。因此，状态转移方程是解决动态规划的关键。
总结一下两种解题思路：
- 回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码
- 找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码
总结与对比
下面分析下四种算法思想——贪心、分治、回溯和动态规划，看它们之间有什么区别和联系。
若将这四种算法思想分一下类，那么贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类。因为前三个算法解决问题的模型，都可以抽象成本节的多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。
