该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 抽象数据类型 VS 数据结构
2. 向量ADT
2.1 有自己的一套接口操作
2.2 可扩充性
-
静态空间管理 Static Memory Management
静态空间管理 动态空间管理 Dynamic Memory Management
思路：即将上溢时，容量加倍
为什么是容量加倍策略而不是容量递增个常数而已呢？
容量递增 -> 每次扩容操作的amortized time 为O(N)
容量加倍 -> 每次扩容操作的amortized time 为O(1)
容量递增 VS 容量加倍
- 加倍扩容的耗时仅为紫色条的和
- 加倍扩容是牺牲一定的空间利用率来换取时间的效率
3. 分摊复杂度
举个🌰：
在扩容分析的中，若只考虑独立操作，那么最坏情况复杂度都为O(N)（递增扩容中由n-1扩到n；加倍扩容由n/2到n)
然而，考虑了连续的一系列操作时，单次递增扩容的分摊时间为O(N^2 / N) = O(N)；加倍扩容的分摊时间为O(N / N) = O(1)。✌️
4. 无序向量
实现了各种对应的操作...
其中一个比较有趣的是deduplicate() ---> 无序向量remove duplicate
- 算法1：暴力
思路：从前往后check每个元素，在它之前的元素中查重。若有重复，remove它，后面元素前移；若无重复，check下一个元素。
时间复杂度：O(N^2)
优化1：减少元素移动的次数
思路：先对要删除的元素的标记，之后再统一删除。
好处：保持了unique元素的稳定性。
时间：O(N^2) 比较次数没有变优化2：利用排序
思路：因为重复元素肯定紧邻，因此可以在O(1)时间内找到duplicate
时间：O(NlgN)
5. 有序向量
5.1 有序性以及逆序程度
5.2 去重uniquify()
- 高效 O(N)
- 思路：双指针
-
关键："隐式删除"
需要删除的元素（即重复元素）并不会直接被remove，因此不会导致之后元素的前移。当发现非重复元素时，把该元素直接赋值到与之比较的元素之后，因此它们之前重复的元素相当于“被删除了”！
有序向量高效去重
5.3 二分查找 search(e, lo, hi）--版本A
-
原理
二分原理 -
实现
实现 -
复杂度 O(lgN)
二分复杂度 -
更精细的分析-查找长度
抠系数分析 O(1.5lgN)
查找长度
5.4 Fibonacci 查找
-
原理
Fib查找原理
与二分查找的本质区别：pivot(即mid)按黄金分割比例取
-
实现
Fib查找实现 -
复杂度-在系数上优于二分
Fib查找长度
5.5 二分查找--版本B
- 原理
- 思路：对于每个向量(即每个比较区间)，无论向左还是向右，需要的比较长度都是1。
-
关键：只有两个分支：要么[lo, mi),要么[mi, hi]，没有对x[mi]的比较。只有在hi - lo == 1是才终止。
原理
5.6 二分查找--版本C
该版本能够满足语义约定
-
语义约定
语义约定 -
实现
-
关键：
要么[lo, mi)，要么(mi, hi]；hi - lo == 0时终止
实现
-
5.7 插值查找 Interpolation Search
-
原理
思路：按照个元素的概率分布来确定pivot（即mid）的取值
关键：秩的比例与值得比例一致
差值查找
举个形象的🌰：比如我们事先知道，一本字典中每个字母的所有单词所占的篇幅可能是一定的，比如说50页，那么我们要查一个以b开头的单词时，不用将mid设为字典的重点或者黄金分割点来查，可以将它设为字典中大概2/26的位置。 -
性能
最好：O(1)
最坏：O(N)
平均：O(lg(lgN))
缺点：易受到“干扰”
插值查找效率
问题规模以开方的方式递减，这样的复杂度如何分析？
【字宽折半分析法】
可以把n映射为为计算机中二进制数的字节长度lgN。因此，问题规模以开方的方式减少，相当于字节长度减半。因此相当于是在lgN的基础上问题规模不断减半，因此是lg(lgN)
5.8 关于各查找算法的使用
6 �无序向量到有序向量：排序
6.1 冒泡排序 Bubble Sort
思路：无序部分在前，有序部分在后。有序部分不断增加，无序部分不断减少。
实现1：扫描N次，每次把扫描区间内最大的元素排在区间最后。
缺点：必须扫描N次，若区间内大部分元素是有序的话，则实际上没比必要扫描这么多次。即扫描了一定次数后区间就已经有序了。-
改进1：扫描的过程中判断扫描区间是否已经sorted，如果是，则不需要进一步扫描，可以及时退出。
关键：利用一个标志sorted来说实现对扫描区间是否已经有序的判断。
冒泡排序-改进1 -
改进2：若区间的只有前一小部分是无序的，后缀一大部分是有序的，那么实际上只需要对前面这一小部分进行扫描交换。
关键：hi跳过已经有序的后缀部分
冒泡排序-改进2 -
性能对比
- 效率：最好O(N)，最坏O(N^2)。不同的算法只在各自的特例中才能有各自的优势。
- 稳定性Stability：相同元素的相对顺序是否能得到保证。
由于只有在大小差异的情况下才能有交换，因此是稳定的。
冒泡排序性能分析
6.2 归并排序 Merge Sort
-
原理
利用分治的思想进行：排序 + 归并
归并排序原理 排序：利用递归知道递归基（即只含有1个元素）
-
二路归并（2-way merge）
-
思想
二路归并思路 -
实现
关键：3个指针i, j, k
i -> 合并向量A中待填充位置
j -> 子向量B中待比较元素的位置
k -> 子向量C中待比较元素的位置
二路归并实现 -
性能
最好与最坏：O(NlgN)
归并排序性能
-
