TsingHuaDSA-向量

2016-10-26  本文已影响0人  kevinscake

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

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

抽象数据类型 VS 数据结构

2. 向量ADT

2.1 有自己的一套接口操作

向量接口操作

2.2 可扩充性

思路:即将上溢时,容量加倍

动态空间管理

为什么是容量加倍策略而不是容量递增个常数而已呢?
容量递增 -> 每次扩容操作的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

deduplicate()暴力实现

时间复杂度:O(N^2)


时间复杂度

5. 有序向量

5.1 有序性以及逆序程度

有序性

5.2 去重uniquify()

5.3 二分查找 search(e, lo, hi)--版本A

5.4 Fibonacci 查找

与二分查找的本质区别:pivot(即mid)按黄金分割比例

5.5 二分查找--版本B

实现

5.6 二分查找--版本C

该版本能够满足语义约定

5.7 插值查找 Interpolation Search

问题规模以开方的方式递减,这样的复杂度如何分析?
【字宽折半分析法】
可以把n映射为为计算机中二进制数的字节长度lgN。因此,问题规模以开方的方式减少,相当于字节长度减半。因此相当于是在lgN的基础上问题规模不断减半,因此是lg(lgN)

5.8 关于各查找算法的使用

查找综合对比

6 �无序向量到有序向量:排序

6.1 冒泡排序 Bubble Sort

6.2 归并排序 Merge Sort

上一篇 下一篇

猜你喜欢

热点阅读