这篇文章记录了我学习列表找到的一些有用的资料以及edX上Data Structures and Algorithms第二周的笔记.
接口与实现
1.ADT/implementation
2.Abstract Data Type vs Data Structure
(1)ADT = 数据模型 + 定义在该模型上额度一组操作
(抽象定义,外部逻辑特性,不考虑复杂度,不涉及数据储存方式)
(2)数据结构 = 基于某种特定语言,实现ADT的一整套算法
(具体实现,完整算法,考虑复杂度,考虑数据储存机制)
3.从数组到向量
(1)Array的每一个元素都可直接访问
(2)A[i]=A+i*s (s为单个元素占用的空间量)
(3)故称作线性数组(linear array)
4.向量是数组的抽象与泛化,由一组元素按现行次序封装而成
(1)各元素与[0,n)内的秩(rank)一一对应 (call-by-rank)
(2)元素的类型不限于基本类型
5.ADT操作实例
(1)disordered():输出逆序对(inversion)的个数
(2)search():返回不超过输入元素(parameter)的最大的那个元素的最后的rank
(3)uniquify():删除有序的向量重复的元素
6.Vector 模板类
/*Vector*/
typedef int Rank; //秩
#define DEFAULT_CAPACITY 3 //默认初始向量(实际应用中可设置为更大,大概32?)
template<typename T>
class Vector{
private:
Rank _size; //规模
int _capacity; //容量
T * _elem; //数据区
protected:
/*...内部函数*/
public:
/*构造函数*/
/*析构函数*/
/*只读接口*/
/*可写接口*/
/*遍历接口*/
}
//构造函数
Vector<T>::Vector(int c = DEFAULT_CAPACITY){ //默认构造函数
_elem = new T[_capacity = c];//首地址交给_elem
_size = 0;
}
Vector::Vector(T const * A,Rank lo,Rank hi){ //数组区间复制
copyFrom(A,lo,hi);
}
Vector<T>::Vector(Vector<T> const & V,Rank lo,Rank hi) //向量区间复制
{
copyFrom(V._elem,lo,hi);
}
Vector<T>::Vector(Vector<T> const & V){ //向量整体复制
copyFrom(V._elem)
}
Vector<T>::~Vector(){ //析构
delete [] _elem;
}
//*关键:copyFrom
template<typename T>
void Vector<T>::copyFrom(T* const A,Rank lo,Rank hi){
_elem = new T[_capacity = 2*(hi-lo)]; //2倍空间,
//可以hi-lo是因为[lo,hi)是[闭,开)空间
_size = 0; //规模清0
while(lo < hi){ //A[lo,hi) traverse
_elem[_size++] = A[lo++]; //复制至_elem[0,hi-lo)
}
}
可扩充向量
1.目前静态空间管理,容量capacity固定,有缺陷
(1)上溢(overflow): elem[]空间不够,尽管系统仍有足够空间
(2)下溢(underflow):elem[]元素很少,装填因子(load factor) lambda = _size/capacity << 50%
*一般应用环境难以准确预测空间的需求量
2.动态空间管理
(1)在即将发生overflow时,适当地扩大内部数组的容量
/*扩容算法*/
template <typename T>
void Vector<T>::expand(){ //向量空间不足时扩容
if(_size < _capacity) return;
//_size == _capacity的时候就扩容
_capacity = max(_capacity,DEFAULT_CAPACITY); //不低于最小容量
T * oldElem = _elem;
_elem = new T[_capacity <<= 1]; //左移,容量加倍, 应该写成_capacity<<1吧?
for(int i=0;i<_size;i++){
_elem[i] = oldElem[i]; //T为基本类型,或已重载'='
}
delete [] oldElem; //释放原空间
}
//优势:封装性
//扩容之后数据区物理地址有所改变,却不会出现野指针
//一般数组动态重新分配地址后,原先指向它内部某些元素的一些指针可能无效,
//虽然它指向一个地址,但其中并没有存放我们所需要的数值
//e.g. *(array +3)指向第三个元素,重新分配后失效,
// *(vector+3)依然能指向第三个元素,都是用_elem统一指示
(2)一个关注点
//是否可以将向量扩容代码中的：
for (int i = 0; i < _size; i++) _elem[i] = oldElem[i];
//替代为：
memcpy(_elem, oldElem, _size * sizeof(T));
/*答案*/
//当T为非基本类型且有对应的复制构造函数以执行深复制时，前一段代码会调用复制构造函数而后一段只能进行浅复制。
3.递增式扩容 (incrementing)
(1)追加固定数额
T * oldElem = _elem;
_elem = new T[_capacity += INCREMENT];
//每经过INCREMENT次插入,都得扩容
//总体耗时:0,I,2I,...,(m-1)I=( (m-1)I+0 )*m/2 = O(n^2) (总和是末项的平方)
//每次分摊成本O(n)
4.容量加倍策略 (doubling)
T * ldElem = _elem;
_elem = new T[_capacity<<1];
//每经过n = 2^m 次插入,就扩容
//总体耗时:1,2,4,...,2^m = O(n) (总和和末项是等阶的)
//每次分摊成本:O(1)
5.分析这两种策略
递增策略 倍增策略
累计时间: O(n^2) O(n)
分摊时间: O(n) O(1)
load factor: ~100% >50%
//倍增策略load factor=50%的时候是即将发生overflow刚加倍扩容的瞬间
//doubling是通过空间的效率做了一个适当的牺牲,换取时间方面巨大的收益
6.平均分析 vs 分摊分析
1.平均复杂度/期望复杂度(average/expected complexity)
(1)根据各种操作出现概率的分布,将对应的成本加权平均
(2)割裂了操作之间的相关性和连贯性
(3)不能准确评判数据结构和算法的真实性能
2.分摊复杂度(amortized complexity)
(1)对数据结构连续地实施足够多次操作,所需总体成本分摊至单次操作
(2)从实际角度做整体考量
(3)忠实刻画可能出现的操作序列
(4)更为精准地评判真实性能
无序向量
1.向量模板
template <typename T> Vector{}
Vector<int/float/double> myVector;
Vector<BinTree> forest;
2.元素访问
/*overload operator[]*/
template <typename T> //0 <= r < _size
T & Vector<T>::operator[](Rank r) const
{
return _elem[r];
}
/*call by rank*/
//此后对外的V[r]即对应于内部的V._elem[r]
//右值: T x = V[r]+U[s]*W[t];
//左值: V[r]=T(2*x+3);
3.插入
template <typename T>
Rank Vector<T>::insert(Rank r,T const & e){ //O(n-r)
expand();//if necessary
for(int i=_size;i>r;i--){ //自后向前
_elem[i] = _elem[i-1];
_elem[r] = e;
_size++;
}
return r;
}
4.区间删除
/*删除区间[lo,hi)*/
template <typename T>
int Vector<T>::remove(Rank lo,Rank hi){ //O(n-hi),把区间后面的元素left shift
if(lo==hi) return 0;
while(hi<_size)
_elem[lo++] = elem[hi++];
_size = lo; //这里因为lo++了之后变成区间最大的位置指示了
shrink(); //更新规模,有必要则shrink
retrun hi-lo; //返回被删除元素的数目
}
5.单元素删除
(1)区间删除操作的特例 [r] = [r,r+1)
template <typename T>
T Vector<T>::remove(Rank r){
T e = _elem[r];
remove(r,r+1);
retrun e; //返回被删除元素
}
6.查找
//无序向量: T为可判等的基本类型,或已重载操作符'=='或'!='
//有序向量: T为可比较的基本类型,或已重载操作符'<'或'>'
template <typename T>
Rank Vector<T>::find(T const & e,Rank lo,Rank hi) const { //找到多个元素时返回rank最大者
while( (lo<hi--)&&(e!=_elem[hi]) );
return hi; //hi<lo意味着失败
}
//输入敏感的算法(input sensitive):
//最好O(1),最坏O(n)
7.唯一化(deduplicate)
(1)应用实例:网络搜索的局部结果经过去重操作(not redundant)
/*删除重复元素,返回被删除元素数目,繁琐版+错误版*/
template <typename T>
int Vector<T>::deduplicate(){
int oldSize = _size;
Rank i = 1;
while(i<_size){
(find(_elem[i],0,i)<0)?i++:remove(i);
}
return oldSize - _size;
}
//分析:
//find遍历前面,remove遍历后面
//所以整个复杂度是O(n^2)
//进一步优化:
//1.标记需删除的重复元素,统一删除:比对操作增加
//2.V.sort().uniquify(),O(nlogn)
8.遍历
(1)遍历向量,统一对各元素visit
-如何指定visit并且传到向量内部?
/*
visit ver1
函数指针,只读或局部性修改
*/
template<typename T>
visit Vector<T>::traverse( void (*visit)(T &) ){ //function pointer
for(int i=0;i<_size;i++){
visit(_elem[i]);
}
}
/*
visit ver2
函数对象,全局性修改
通用性更强
*/
template <typename T> template<typename VST>
void Vector<T>::traverse(VST & visit) //函数对象function object,overload bracket()
{
for(int i=0;i<_size;i++){
visit(_elem[i]);
}
}
/*实例*/
//对所有元素分别+1
//首先实现一个可使单个T类型元素+1的类
//假设T可直接++或已重载"++"
template <typename T>
struct Increase{
virtual void operator(T & e){
e++;
}
}
//此后
template <typename T>
void increase(Vector<T> & V){
V.trverse(Increase<T>());
}
有序向量:唯一化 (ordered vector:uniquify?)
1.有序性及其甄别
(1)有序序列,任意一对相邻元素顺序
(2)无序序列,总有一对元素逆序(inversion)
(3)相邻逆序对的总数,可以度量向量的逆序程度
template <typename T>
int Vector<T>::disordered() const {
int n = 0; //counter
for(int i=1;i<_size;i++){
n += (_elem[i-1]>_elem[i]); //有inversion就计数
}
return n; //向量有序iff n==0
}//若只需判断是否有序,首次遇到inversion后可终止
2.唯一化
/*低效版*/
template<typename T>
int Vector<T>::uniquify(){ //uniquify只针对有序的
int oldSize = _size;
int i = 0;
while(i<(_size-1)){
(_elem[i]==_elem[i+1])?remove(i+1):i++;
}
return oldSize - _size;
}//O(n^2)
/*高效版*/
template <typename T>
int Vector<T>::uniquify(){
Rank i=0,j=0;
while(++j<_size){
if(_elem[i] != _elem[j])
_elem[++i] = _elem[j];
}
_size = ++i;
shrink();
return j-i;
}//O(n)
二分查找
1.语义约定
(1)便于有序向量自身的维护:V.insert(1+V.search(e),e) (确保插入后还是有序向量,即使失败,也需要给新元素插入的适当位置)
(2)前人的方法,在V[lo,hi)中,确定 不大于(<= less than or equal)e的最后一个 元素的rank
-若e< V[lo],返回lo-1
-若e>V[hi-1],返回hi-1
/*binary search ver1*/
template<typename T>
static Rank binSearch(T * A,T const & e,Rank lo,Rank hi){
while(lo<hi){
Rank mi = (lo+hi)>>1; //以中点为轴
if (e<A[mi]) hi = mi; //建议都用小于号,因为和左右次序吻合
else if(A[mi]>e) lo = mi+1;
else return mi;
}
return -1; //查找失败,可以优化
}O(logn)
更为精细地评估查找算法的性能:
(1)考察渐近复杂度logn前面的那个常系数-考察关键码的比较次数,即查找长度(search length) (其实就是在其中执行的if语句的次数)
(2)版本1,平均查找长度大约是O(1.5logn)
(3)每次大概都要if判断1.5次,所以还能改进
Fibonacci查找
1.二分查找ver1的效率仍有改进余地,因为转向左,右分支前的关键码比较次数不等,而递归深度却相同
(向左侧比较1次,右侧却要2次;所以可以把往左边的查找次数多增加一些)
2.若能通过递归深度的不均衡,对转向成本的不均衡进行补偿,平均查找长度能进一步缩短
3.比如,若设n=fib(k)-1,则可取mi=fib(k-1)-1,
于是前后子向量的长度分别是:fib(k-1)-1,fib(k-2)-1
/*Fibonacci search*/
template <typename T>
static Rank fibSearch(T * A,T const & e,Rank lo,Rank hi){
Fib fib(hi-lo); //用O(logn)=O(log(hi-lo))时间创建Fib数列
while(lo<hi){
while(hi-lo<fib.get()) fib.prev();
//通过向前顺序查找,确定形如 Fib(k)-1的轴点
Rank mi = lo + fib.get() - 1;
if (e<A[mi]) hi = mi;
else if (A[mi]<e) lo = mi+1;
else return mi;
}
return -1;
}
4.查找长度
(1)Fibonacci查找的ASL(average search length),在常系数的意义上由于binary search
5.0.618
(1)通用策略:对于任何的A[0,n),总是选取A[lambda*n]作为轴点(pivot)
(2)binary search : lambda = 0.5
(3)Fibonacci search: lambda = 0.618
(4)最优lambda:
设平均查找长度为alpha(lambda)*logn,使得alpha(lambda)最小
lambda=0.618
二分查找(改进) Binary search
1.二分查找中左,右分支转向代价不平衡,可直接解决
2.比如每次迭代(递归),仅作1此关键码比较,所有分支只有2个方向,而不再是3个
3.轴点(pivot)mi取作重点,
(1)e < x, 深入S[lo,mi)
(2)x <=e, 深入S[mi,hi)
(3)当元素数目hi-lo=1时,才判断该元素是否命中
4.实现
/*binary search ver2*/
template<typename T> static Rank binSearch(T * A,T const & e,Rank lo,Rank hi){
while(1<hi-lo){
Rank mi = (lo+hi)>>1;
(e<A[mi])? hi=mi:lo=mi; //[lo,mi) or [mi,hi)
}//出口时hi=lo+1,查找区间仅含一个元素A[lo]
return(e==A[lo]) ? lo:-1;
}
//相对于ver1,最好情况下更坏,最坏情况下更好:各种情况下Search Length更加接近,整体性能更稳定
5.语义定义
(1)search语义约定:返回不大于e的最后一个元素 (收敛之后S[lo-1])
(2)支持相关算法: V.insert(1+V.search(e),e)
/*Binary search ver3 近乎完美*/
template <typename T> static Rank BinSearch(T * A,T const & e,Rank lo,Rank hi){
while(lo<hi){ //不变性A[0,lo)<=e<A[hi,n)
Rank mi = (lo+hi)>>1;
(e<A[mi])? hi=mi:lo=mi+1; //[lo,mi) or [mi+1,hi)
}
return --lo; //lo-1即为不大于e的元素的最大rank
}
//与ver2的差异
//(1)待查找区间宽度缩短至0而非1时,算法才结束
//(2)转入右侧子向量时,左边界取作 mi+1 而非mi,A[mi]会被遗漏? (不会的,因为在右区间搜完了返回--lo刚好就停在A[mi])
//(3)无论成功与否,返回的rank严格符合接口的语义约定
补充材料:
C++中的static:
静态函数与普通函数不同，它只能在声明它的文件当中可见，不能被其它文件使用。
http://www.360doc.com/content/09/0919/15/61809_6173677.shtml