- O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”，准确的定义请参考相关专业书籍。重点在于，通过这种表示方法，我们可以直观地了解算法的时间复杂度
- 当我们知道选择排序的时间复杂度为O（n2）、快速排序的时间复杂度为O（nlogn）时，很快就能判断出快速排序的运算更为高速。二者的运行时间根据输入n产生的变化程度也一目了然。
一、链表
二、数组
三、栈
四、队列
五、哈希表
六、堆
- 堆是一种图的树形结构，被用于实现“优先队列”（priority queues）
- 优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出
- 如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。
七、二叉查找树
- 二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构
- 二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。
- 有很多以二叉查找树为基础扩展的数据结构，比如“平衡二叉查找树”。这种数据结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。
- 种子结点数可以自由设定，并且形状均衡的树便是B树。
图
- 由顶点和连接每对顶点的边所构成的图形就是图。
- 这个值叫作边的“权重”或者“权”，加了权的图被称为“加权图”。没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程度”
- 有向图、无向图
广度优先搜索
- 广度优先搜索会优先从离起点近的顶点开始搜索。
- 候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。
- 广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。
深度优先搜索
- 深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。
- 此处，候补顶点是用“后入先出”（LIFO）的方式来管理的，因此可以使用“栈”这个数据结构。
- 广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。
贝尔曼-福特算法
- 贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。
- 贝尔曼也因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。
狄克斯特拉算法
- 狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。
A*算法
- A（A-Star）算法也是一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A就会预先估算一个值，并利用这个值来省去一些无用的计算。
Reference
- [我的第一本算法书] - 宫崎修一 石田保辉