渐进算法
编写有效率的程序主要分为两个方面，一方面是编程花费：程序开发时间，易读性，易修改性以及易维护性。另一方面是程序执行花费包括时间复杂度和空间复杂度。
要比较算法的时间复杂度：只考虑最坏的情况，选择程序中最具有代表性的语句的时间，去掉低阶项和常数。大Θ表示法R（N）∈Θ（f(N)）;并且有k1⋅f(N)≤R(N)≤k2⋅f(N)；
- 大O表示法则要求R(N)≤k2⋅f(N)
- 大Ω算法则表示k1*f(N)<=R(N)
嵌套循环的时间复杂度不一定是(N^2)；课程中讲述了一个递归算法：
public static int f3(int n){
if( n <= 1 )
return 1;
return f3(n-1) + f3(n-1);
}其时间复杂度为(2^N )- 1即为θ（2^N）;
二分查找法最坏的情况下时间复杂度为log2（N） + 1即为Θ（log（N））；归并排序法的思想是不断将数组拆分成两个子数组然后从两个子数组中排序最后层层合并为原来的排序好的数组的方法。其时间复杂度与层数以及数组的长度有关，时间复杂度为θ（Nlog(N)）。
最后讲了摊销分析，以数组添加时的resize方法为例。可以使得整体上复杂度在以上常数以下。最后还介绍了分析方法。
不相交集（Disjoint Sets）
两个不相交集之间关系大致可以看作零个集合，可以用{0，1，2，4}，{3，5}表示。
不相交集应该包括以下方法：
void connect(int p,int q);
boolean isConnected(int p,int q);可以通过array的方式实现不相交集.每个索引表示元素，索引值为所属于的集合。索引值相同的两个元素存在于集合中。
这种实现使得isconnected方法只需要比较索引值即可，但会使得connect方法速度很慢，因为要修改一个集合中所有元素对应数组索引的值。
可以通过修改disjointset实现的方式来实现quick-union。数组中每个元素的值是该元素连接的下一个元素,并选择一个元素作为根元素，相同集合中的元素最终都会间接或直接的连接至此元素，根元素的链接为自身,形成了一个树。
要连接两个集合只需要将一个集合的根元素的值连接到另一个集合的根元素上。这个改进使得connect方法操作达到了线性级别。但与树的深度有关，树的形状会对算法速度产生很大影响。
加权的quick-union算法通过添加一个数组记录书中的节点树，在connect中总是将小树链接到大树上面。基于此又产生了基于路径压缩的加权quick-union算法。
二叉查找树（Binary Search Trees）
每个节点的键都大于左子树小于右子树。
将一个有序的表转换为二叉查找树，结合其特点查找算法效率会大大提高。
主要方法包括查找，插入和删除。
删除方法主要分为三种情况：
1.删除键无子树 -- 直接删除即可；
2.删除键有一个子树 -- 父节点与删除键的链接修改为指向删除键的子树；
3.删除键有两个子树 - 将删除键左子树中最右的节点或右子树最左的节点移动至删除键的位置【保证树的特性】。
在算法第四版中这也部分另外地介绍了选择，排序，最大键与最小键，取整，等方法。
散列
散列主要包括散列函数将输入转换为一个索引，以及处理碰撞的过程。处理碰撞时提到了负载因子。
最简的散列函数便是除留余数法。
处理碰撞主要包括拉链法（将冲突的元素保存在链表中，散列表的值指向链表的地址）和线性探测法（将冲突的元素放至附近空的节点中）。
堆/优先队列
二叉堆：每个节点都小于其子节点；（完备性）缺失的元素仅在树底部出现且所有元素都尽习能在左子树。
添加节点（元素）：临时放到二叉树的底部然后根据规则使用上浮交换操作，直到符合规则。
删除最小元素（根节点）：将节点删去后，让最底部的节点作为根节点并不断下沉交换直到使整个树符合规则。
树在Java中的表示：N叉树对应列表节点k父节点的序号为 (k-1)/n｡ （根点位于索引0处）
与树中相似的下沉和上浮操作。
先进树、几何
遍历
顺序访问：每一层从左往右访问每个节点；
深度优先：分为前序，中序和后序。中左右，左中右，左右中；对于多叉树不存在中序遍历。直接使用递归实现。
访问者模式
范围搜索：搜索树中大小在一定范围内的节点；2维范围搜索：用不同的象限表示分支；
剪枝：限制搜索仅仅在可能包含结果的节点。
图（Graphs）
图：一系列由边连接起来的节点构成图。有向图、无向图、带权重图。图来表示非等级关系。
简单图表示不包含环和平行边
图的实现：1．使用邻接矩阵； 2. 边的集合；3．邻接数组；
深度优先搜索：先探学某子节点对应的子树
图遍历
遍历方法包括深度优先前序，深度优先后续和广度优先。
图遍历通常不唯一，但树遍历是唯一的。
广度优先使用一个队列，深度优先使用的是栈。在cs61B的视频中添加了个计算各个节点到起始点的距离。
讨论图数据结构的实现对于api实现的方法的速度的影响。
最短路径
Dijkstra算法
将 distTo[] 最小的非树顶点放松并加入树中，如此这般，直到所有的顶点都在树中或者所有的非树顶点的 distTo[] 值均为无穷大。
寻找加权有向图从起点到其他每一个节点的最短路径。最终的答案通常是一个树。（即不包含环，且每个节点都只有一个父节点），由此当所有节点可达时包含的边数为节点数为 节点数-1
- 松弛法
先将其他的有节点距起始节点的距离没置为无穷大，起始节点为0。
以深度优先顺序从源节点开始找距离源节点最近的点访问（与深度优先并不相同），每次删除优先队列中的距离初始点最近的点。
当节点到初始节点为最短路径时从优先队列中删除该节点，松驰每一个访问的节点。
- A＊算法
课程中提到对于要寻找途中一个点到另一个点的最短路径，如若存在从初始节点到中间节点的最短路径，可以假设该路径时从起点到终点最短路径的一部分。
最小生成树
讨论带权重无向图的最小生成树；
最小生成树：连接，无环（树的性质）、包含所有的节点（所有边权重之和尽可能小）
最短路径根据起始节点不同，路径不同。但最小生成树没有起始节点。
切分定理
横切边：将两个点的集合区别开来的边；横切边中最小权重边一定属于最小生成树。
最小生成树算法 Prim
随意从每个点开始，以该点为子集，添加权重最小的一条横切便至MST中；重复添加V-1条边。
横切边权重最小值存在多条时添加其中一条；同时此时MST并非是唯一的。
使用优先队列存储所有的边（以距离树的距离），每次从队列中删除距离最小的点并松弛指向该点的所有边。
Prim考虑的时距离MST的距离；Dijkstra考虑的是到起始点的距离。
Krukal算法
利用union-find数据结构判断是否可以生成环【所有节点均可达】。
以权重升序排序边，并将不会产生环的边（不连接的两个点）加入到MST，直到有V-1个边。【多了一定会产生环】
动态规划（Dynamic Programing）
有向无环图DAG：可以被拓扑排序（线性化）；很容易找最短路径。不需要在意距离初始节点的距离，只需要按拓扑顺序访问并松驰。
动态规划：把大问题分解成子问题，通过一个个子问题的解决最后解决大问题。
动态规划特点
分治是算法中的一种基本思想，其通过将原问题分解为子问题，不断递归地将子问题分解为更小的子问题，并通过组合子问题的解来得到原问题的解。
类似于分治算法，动态规划也通过组合子问题的解得到原问题的解。不同的是，适合用动态规划解决的问题具有重叠子问题和最优子结构两大特性。
重叠子问题
动态规划的子问题是有重叠的，即各个子问题中包含重复的更小子问题。若使用暴力法穷举，求解这些相同子问题会产生大量的重复计算，效率低下。
动态规划在第一次求解某子问题时，会将子问题的解保存；后续遇到重叠子问题时，则直接通过查表获取解，保证每个独立子问题只被计算一次，从而降低算法的时间复杂度。
最优子结构:如果一个问题的最优解可以由其子问题的最优解组合构成，并且这些子问题可以独立求解，那么称此问题具有最优子结构。
动态规划从基础问题的解开始，不断迭代组合、选择子问题的最优解，最终得到原问题最优解。
动态规划解题框架
若确定给定问题具有重叠子问题和最优子结构，那么就可以使用动态规划求解。总体上看，求解可分为四步：
- 状态定义： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
- 初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
- 转移方程：确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
- 返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；
