TsingHuaDSA-向量

该文章为清华大学数据结构与算法设计MOOC课程读书笔记.

1. 抽象数据类型 VS 数据结构

抽象数据类型 VS 数据结构

2. 向量ADT

2.1 有自己的一套接口操作

向量接口操作

2.2 可扩充性

• 静态空间管理 Static Memory Management

  
  静态空间管理

• 动态空间管理 Dynamic Memory Management

思路：即将上溢时，容量加倍

动态空间管理

为什么是容量加倍策略而不是容量递增个常数而已呢？
容量递增 -> 每次扩容操作的amortized time 为O(N)
容量加倍 -> 每次扩容操作的amortized time 为O(1)

容量递增 VS 容量加倍

• 加倍扩容的耗时仅为紫色条的和
• 加倍扩容是牺牲一定的空间利用率来换取时间的效率

3. 分摊复杂度

平均复杂度 VS 分摊复杂度

举个🌰：
在扩容分析的中，若只考虑独立操作，那么最坏情况复杂度都为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下一个元素。

deduplicate()暴力实现

时间复杂度：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)

    
    归并排序性能