算法设计与分析
选择排序
每一轮选择最小的那个 一个简单的两重循环。
冒泡排序
也是一个两重循环，但是每次只要剩余数中的最小值。
时间复杂度为 O(n^2)
顺序查找
用一个 target 来做一个限定。
蛮力字符串匹配
无脑循环，如果模式串中和匹配串中的不匹配直接往前走。
最近对问题
一个简单的初中数学问题，通过计算两数距离即可，甚至可以不用开平方根简化计算。
时间复杂度为 O(n^2)
凸包问题
问题：对于平面上 n 个点，找包围它们的最小凸多边形。
蛮力算法：对于每对点 p1 和 p2，判断是否所有其他点都在连接 p1 和 p2 的直线的同一侧;
算出直线 y = ax + b 即可，将所有点带到这个直线中判断符号是否相同。
时间复杂度为 O(n^3)
旅行商问题
值得一提的一个点是可以看到有三对不同的路线，每对路线之间仅有方向不同，因此可以把顶点排列的数量减半。
背包问题
教材上的图就是一个简单的图表，这边比较重要的点是用穷举法解决背包问题需要 O(2^n) 的时间复杂度。他和上面的旅行商问题都是典型的 NP 困难问题。
深度优先查找
V 和 E 分别为图的顶点和边的数量。数据结构为栈，顶点顺序有两种。
广度优先查找
V 和 E 分别为图的顶点和边的数量。数据结构为队列，顶点顺序只有一种。
插入排序
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
最坏时间复杂度与平均时间复杂度均为 O(n^2)，最好时间复杂度为 O(n)。
拓扑排序
拓扑排序这里提供了两种解法，分别是 DFS 遍历栈和基于减治技术的算法。
减治技术会在每次迭代时，删除没有输入边的节点。
生成排列
满足最小变化要求。
时间复杂度为 O(n!)，生成的排序不为字典序。
生成子集
能够生成 2^n 个子集，也就是幂集。后一组的每一个元素都可以通过把 a(n) 添加到 {a(1) ... a(n - 1)} 中子集来获得。
折半查找
经典二分问题
俄式乘法
仅有折半、加倍以及相加三个操作，硬件实现非常快速。
选择问题
插值查找
插值查找计算要查找的值在数组中的大致位置，然后将数组分为两部分，其中一部分必定不可能包含要查找的值，另一部分可能包含要查找的值，然后在可能包含要查找的值的那一部分中继续递归查找，直到找到要查找的值或者确定要查找的值不存在于数组中。
在数组分布不均匀的情况下，它的效率可能会比二分查找还低。
分治法适用条件
原始可分解，且分解出来的子问题和原始问题就有相同的类型。
分解出来的子问题到很小时可以很容易（在很短的时间和空间内能求解）求解。
子问题的解能合并。
归并排序
归并排序的平均时间复杂度也是 O(nlogn)。最好和最坏情况下的时间复杂度都是 O(nlogn)。
快速排序
平均时间复杂度也是 O(nlogn)。最好情况下，即每次都能平分数组，时间复杂度为 O(nlogn)；最坏情况下，即每次划分只能减少一个元素，时间复杂度为 O(n^2)。但是最坏情况发生的概率非常小，所以快速排序通常被认为是一种非常高效的排序算法。
大数乘法
预排序
检查数组中元素的唯一性
先排序再比对是否唯一，时间复杂度基于排序 O(nlogn)。
霍纳法则
动态规划解决背包问题
最优二叉查找树
Warshall
R[i][j][k] == R[i][j][k - 1] || R[i][k][k - 1] && R[k][j][k - 1]
Floyd
D[i][j] == min(D[i][j], D[i][k] + D[k][j])
哈夫曼编码
二叉树左分支为 0，右分支为 1。
P 类
NP 类
Last updated
