Algorithm_Note
1.什么是算法
在计算机领域内，算法是一系列程序指令，用于处理特定的运算和逻辑问题。
衡量算法优劣的主要标准是时间复杂度和空间复杂度。
2.什么是数据结构？
数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
数据结构包含数、链表这样的线性数据结构，也包含树，图这样的复杂数据结构。
3.什么是时间复杂度？
时间复杂度是对一个算法运行时间长短的量度，用大 O O O表示，记作 T T T(n)= O O O( f f f(n))。
常见的时间复杂度按照从低到高的顺序，包括 O O O(1)、 O O O(log n n n)、 O O O(n)、 O O O( n n nlog n n n)、 O O O(n²)等。
4.什么是空间复杂度？
常见的空间复杂度按照从低到高的顺序，包括 O O O(1)、 O O O( n n n)、 O O O( n n n²)等。其中递归算法的空间复杂度和递归深度成正比。
5.什么是数组？
数组是由有限个相同类型的变量所组成低端有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是 O O O(1)，中间插入、删除数组元素的时间复杂度是 O O O)n。
6.什么是栈？
栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则(FILO)。
7.什么是队列？
队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作。遵循先入先出的原则(FIFO)。
8.什么是散列表？
散列表也叫哈希表，是存储 K e y − V l a u e Key-Vlaue Key−Vlaue映射映射的集合。对于某一个 K e y Key Key,散列表可以在接近 O O O(1)的时间内进行读写操作。散列表通过哈希函数实现 K e y Key Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。
9.什么是树？
树是 n n n个节点的有限集，有且仅有一个特定的称为根的节点。当 n n n>1时，其余节点节点可分为 m m m个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
10.什么是二叉树？
二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式。
11.二叉树的遍历方式有几种？
根据遍历节点之前的关系，可以分为前序遍历、中序遍历、后序遍历、层序遍历这4种方式；从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历两大类。
12.什么是二叉堆？
二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。
在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。
13.什么是优先队列？
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入列顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。
在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的。
14.对常见排序算法的复杂度整理
| 排序算法 | 时间复杂度 | 空间复杂度 | 是否稳定排序 |
|---|---|---|---|
| 冒泡排序 | O O O( n n n²) | O O O( 1 1 1) | 稳定 |
| 鸡尾酒排序 | O O O( n n n²) | O O O( 1 1 1) | 稳定 |
| 选择排序 | O O O( n n n²) | O O O( 1 1 1) | 不稳定 |
| 插入排序 | O O O( n n n²) | O O O( 1 1 1) | 稳定 |
| 希尔排序 | Sedgewick增量： O O O( n 4 / 3 n^{4/3} n4/3) | O O O( 1 1 1) | 不稳定 |
| 快速排序 | 平均： O O O( n n nlog n n n)；最坏： O O O( n n n²) | O O O(log n n n) | 不稳定 |
| 堆排序 | O O O( n n nlog n n n) | O O O( 1 1 1) | 不稳定 |
| 归并排序 | O O O( n n nlog n n n) | O O O( n n n) | 稳定 |
| 计数排序 | O O O( n n n+ m m m) | O O O( m m m) | 稳定 |
| 桶排序 | O O O( n n n) | O O O( n n n) | 稳定 |
| 基数排序 | O O O( k k k( n n n+ m m m)) | O O O( n n n+ m m m) | 稳定 |
15.树的进阶知识重要结论梳理
二叉查找树可以提高节点查找的频率，并维持节点的有序性。
理想状态下，二叉查找树查找的时间复杂度是 O O O(log n n n)，但如果节点分布失衡，查找的时间复杂度可能退化到 O O O( n n n)。
平衡二叉树也叫做AVL树，是一种特殊的二叉查找树，可以自动调节平衡。
AVL树维持着严格的平衡，任意节点的两颗子树的高度差都不超过1。这样的优点是保证了查询的效率，缺点是维持平衡的成本比较高，适合查询较多的场景。
红黑树是另一种可以自动调整平衡的二叉查找树。
红黑树维持着相对的平衡，要求任何一条路径的长度不超过其他路径长度的2倍。这样的优点是降低了维持平衡的成本，缺点是查询效率略低，适合频繁插入、删除的场景。
B树解决了从磁盘海量数据中查询的需求，有效减少了磁盘I/O的频次。
B+是B树的升级，叶子节点包括全量数据，并使用双向指针连接相邻节点，为范围查询提供了便利。
16.图的重要结论梳理
- 图是一种多对多的数据结构，最基本的单元是顶点，顶点之间由边关联。
- 无权图的边没有权重的概念；带权图的每一条边拥有自己的权重。
- 无向图的顶点关联是对称的；有向图的顶点关联不完全对称，顶点A触达顶点B，顶点B未必触达顶点A。
- 图的主要存储方式包括邻接矩阵和邻接表/逆邻接表。
- 图的遍历方式，分为深度优先遍历和广度优先遍历。
- 寻找图的单源最短路径，可以使用迪杰斯特拉(Dijkstra)算法；寻找图的多源最短路径，可以使用弗洛伊德(Floyd)算法。
17.查找算法的重要结论梳理
- 在有序数组中查找元素，可以使用二分法查找算法，查找时间复杂度是** O O O(log n n n)**。
- 在有序链表中查找元素，可以把链表改造成跳表，查找的时间复杂度是** O O O(log n n n)**。
- BF算法是朴素的字符串匹配算法，效率较低，时间复杂度是** O O O( m x n mxn mxn)**。
- RK算法利用hash进行字符串匹配，效率较高但不稳定，平均时间复杂度是** O O O( m m m+ n n n)**。
- KMP算法减少了字符串匹配过程中的无谓比较，交流较高且稳定，时间复杂度是** O O O( m m m+ n n n)**。
