【数据结构（邓俊辉）学习笔记】向量04——有序向量_邓俊辉 数据结构 向量 search

0.概述

若向量S[0, n)中的所有元素不仅按线性次序存放，而且其数值大小也按此次序单调分布，则称作有序向量（sorted vector）。

1.比较器

有序向量的定义的先决条件：各元素之间必须能够比较大小和判等操作。这一条件构成了有序向量中“次序”概念的基础，否则所谓的“有序”将无从谈起。

复杂数据对象应重载"<“和”<="等操作符。

2.有序性甄别

算法思想：顺序扫描整个向量，逐一比较每一对相邻元素——向量已经有序，当且仅当它们都是顺序的。

template <typename T> 
int Vector<T>::disordered() const { //返回向量中逆序相邻元素对的总数
	int n = 0; //计数器
	for ( int i = 1; i < _size; i++ ) //逐一检查_size - 1对相邻元素
		if ( _elem[i - 1] > _elem[i] ) n++; //逆序则计数
	return n; //向量有序当且仅当n = 0
}
1
2
3
4
5
6
7

3.唯一化

出于效率的考虑，为清除无序向量中的重复元素，一般做法往往是首先将其转化为有序向量。

3.1低效算法

3.1.1实现

算法思想：

template <typename T> 
int Vector<T>::uniquify() { //有序向量重复元素剔除算法（低效版）
	int oldSize = _size; int i = 1; //当前比对元素的秩，起始于首元素
	while ( i < _size ) //从前向后，逐一比对各对相邻元素
		_elem[i - 1] == _elem[i] ? remove ( i ) : i++; //若雷同，则初除后者；否则，转至后一元素
	return oldSize - _size; //向量规模发化量，即被初除元素总数
}
1
2
3
4
5
6
7

3.1.2 复杂度

分析需用结论：remove()操作的复杂度线性正比于被删除元素的后继元素总数。不清除的可看无序向量。

最坏情况下：
当所有元素均雷同时，用于所有这些remove()操作的时间总量将高达：
(n - 2) + (n - 3) + … + 2 + 1= O($n^2$) 由算术级数得 。不清楚可看算法分析

这一效率竟与向量未排序时相同，说明该方法未能充分利用此时向量的有序性。

3.1.3 改进思路

反思：低效的根源在于，同一元素可作为被删除元素的后继多次前移
启示：若能以重复区间为单位，成批删除雷同元素，性能必能改进。

3.2 高效算法

3.2.1 实现

算法思想：
可以区间为单位成批地删除前后紧邻的各组重复元素，并将其后继元素（若存在）统一地大跨度前移。

template <typename T> 
Rank 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; //向量规模变化量，即被删除元素总数
}
1
2
3
4
5
6
7
8
9

3.2.2 复杂度

由此可知，uniquify()算法的时间复杂度应为O(n)，较之无序向量唯一化算法的O($n^2$)，效率整整提高了一个线性因子。关键在于向量已经排序。

4.查找

4.1统一接口

为区别于无序向量的查找接口find()，有序向量的查找接口将统一命名为search()。外部接口形式上统一，内部实现算法却不见得完全统一。

template <typename T> //在有序向量的区间[lo, hi)内，确定不大于e的最后一个节点的秩
Rank Vector<T>::search( T const& e, Rank lo, Rank hi ) const { // 0 <= lo < hi <= _size
   return ( rand() % 2 ) ? binSearch( _elem, e, lo, hi ) : fibSearch( _elem, e, lo, hi );
} //等概率地随机使用二分查找、Fibonacci查找
1
2
3
4

• 如何处理特殊情况？
  比如，目标不存在；或者反过来，目标元素同时存在多个

4.2 语义定义

在语义上进一步的细致约定，使search()接口作为一个基本部件为其他算法利用。

在有序向量区间V[lo,hi)中，确定不大于e的最后一个元素。

4.3 二分查找

4.3.1 原理

每经过至多两次比较操作，可以将查找问题简化为一个规模更小的新问题。如此，借助递归机制即可便捷地描述和实现此类算法。

4.3.2 实现

算法思想：减而治之

// 二分查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
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; //深入前半段[lo, mi)继续查找
		else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
		else return mi; //在mi处命中
	} //成功查找可以提前终止
	return -1; //查找失败
} //有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地迒回-1，而且能指示失败的位置
1
2
3
4
5
6
7
8
9
10
11

• 通过快捷的整数移位操作回避了相对更加耗时的除法运算。
• 通过引入lo、hi和mi等变量，将减治算法通常的递归模式改成了迭代模式。（递归消除）

4.3.3 复杂度

随着迭代的不断深入，有效的查找区间宽度将按1/2的比例以几何级数的速度递减。经过至多log2(hi - lo)步迭代后，算法必然终止。故总体时间复杂度不超过：
O($lo{g}_2(hi-lo)$) = O(logn)
上图中的递归公式也可得出这个结论，递推公式不熟悉的可以看递推分析。

顺序查找算法的O(n)复杂度相比无序向量的查找find()无序向量，O(logn)几乎改进了一个线性因子（任意c > 0,logn = O($n^c$)）。

4.3.4 查找长度

查找算法的整体效率主要地取决于其中所执行的元素大小比较操作的次数，即所谓查找长度。

通常，需分别针对成功与失败查找，从最好、最坏、平均等角度评估

结论：此版二分查找成功、失败时的平均查找长度均大致为O（1.5logn）

4.3.5 不足

尽管二分查找算法（版本A）即便在最坏情况下也可保证O(logn)的渐进时间复杂度，但就其常系数1.5而言仍有改进余地。

4.4 Fibonacci查找

4.4.1 改进思路

解决问题的思路：

1. 调整前、后区域的宽度，适当地加长（缩短）前（后）子向量
2. 统一沿两个方向深入所需要执行的比较次数，比如都统一为一次

4.4.2 黄金分割

实际上，减治策略本身并不要求子向量切分点mi必须居中，故按上述改进思路，不妨按黄金分割比来确定mi。

4.4.3 实现

算法思路：减治策略——黄金分割比来确定mi

#include "..\fibonacci\Fib.h" //引入Fib数列类
// Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template <typename T> 
static Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi ) {
	Fib fib ( hi - lo ); //用O(log_phi(n = hi - lo)时间创建Fib数列
	while ( lo < hi ) { //每步迭代可能要做两次比较判断，有三个分支
		while ( hi - lo < fib.get() ) fib.prev(); //通过向前顺序查找（分摊O(1)）——至多迭代几次？
		Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点
		if ( e < A[mi] ) hi = mi; //深入前半段[lo, mi)继续查找
		else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
		else  return mi; //在mi处命中
	} //成功查找可以提前终止
	return -1; //查找失败
} //有多个命中元素时，不能保证返回秩最大者；失败时，简单地迒回-1，而且能指示失败的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14

对Fib数不清楚得可以看算法设计优化——Fibonacci数

4.4.4 复杂度分析

进入循环之前调用构造器Fib(n = hi - lo)，将初始长度设置为“不小于n的最小Fibonacci项”。这一步所需花费的O($lo{g}_{\varphi }$n)时间，分摊到后续O($lo{g}_{\varphi }$n)步迭代中，并不影响算法整体的渐进复杂度。

4.4.5 平均查找长度

结论：O(1.44∙log2n)

4.5 通用策略

4.6 结论

• 二分查找算法的时间复杂度O(logn)，平均查找长度O(1.5∙log2n)
• Fibonacci查找算法的时间复杂度O(logn)，平均查找长度O(1.44∙log2n)

Fibonacci查找算法效率略有提高。

二分查找和Fibonacci查找接口均为严格符合search（）接口语义，即返回确定不大于e的最后一个元素得秩，而不是-1。还可改进见有序向量二分查找算法与Fibonacci查找算法