向量

C/C++语言中,数组A[]中的元素与[0, n)内的编号一一对应,反之,每个元素均由(非负)编号唯一指代,并可直接访问,即A[i]的物理地址 = A + i*s, s为单个元素占用的空间量,故亦称作线性数组(linear array)。向量是数组的抽象与泛华,由一组元素按线性次序封装而成,各元素与[0, n)内的(rank)一一对应,我们也称其为循秩访问(call-by-rank);向量操作、管理维护更加简化、统一与安全,元素类型可灵活选取,便于定制复杂数据结构。

首先我们来看一下向量ADT操作接口:

操作 功能 适用对象
size() 报告向量当前的规模(元素总数) 向量
get(r) 获取秩为r的元素 向量
put(r, e) 用e替换秩为r元素的数值 向量
insert(r, e) e作为秩为r元素插入,原后继依次后移 向量
remove(r) 删除秩为r的元素,返回该元素原值 向量
disordered() 判断所有元素是否已按非降序排列,返回非降序对数 向量
sort() 调整各元素的位置,使之按非降序排列 向量
find(e) 查找目标元素e,返回该元素的秩,若未查找到,则返回-1 向量
search(e) 查找e,返回不大于e且秩最大的元素,若未查找到,则返回-1 有序向量
deduplicate(), uniquify() 剔除重复元素 向量/有序向量
traverse() 遍历向量并统一处理所有元素 向量

可扩充向量

对于向量,我们可以开辟内部数组_elem[]并使用一段地址连续的物理空间,令_capacity为向量的总容量,_size为向量当前的实际规模n。若采用静态空间管理策略,容量_capacity固定,则有明显的不足:在空间效率上容易出现上溢(overflow),即_elem[]不足以存放所有元素,尽管此时系统往往仍有足够的空间;或者下溢(underflow),即_elem[]中的元素寥寥无几,此时它的装填因子(load factor),即λ = _size/_capacity就会远远小于50%。更糟糕的是,一般的应用环境中难以准确预测空间的需求量。对此,我们可以采用动态空间管理:在即将发生上溢时,适当扩大内部数组的容量。我们有下面的扩容算法:

请注意,我们这里采用的是容量加倍的策略,其他策略是否可行呢?我们接下来分析一个容量递增的策略,即:

这个算法在最坏情况下,即在初始容量0的空向量中,连续插入n = m*I >> 2个元素,于是,在第1、I+1、2I+1、3I+1、…次插入时,都需扩容,即便不计申请空间操作,各次扩容过程中复制原向量的时间成本依次为0、I、2I、…、(m-1)*I,显然这是一个算术级数,则总体耗时 = I * (m-1) * m/2 = O(n2),每次扩容的分摊成本为O(n)。再回过头看下容量加倍策略,即:

这个算法在最坏情况下,即在初始向量1的满向量中,连续插入n = 2m >> 2个元素,于是,在第1、2、4、8、16、…次插入时都需扩容,各次扩容过程中复制原向量的时间成本依次为1、2、4、8、…、2m = n,显然这是一个几何级数,则总体耗时 = O(n),每次扩容的分摊成本为O(1)。

在前面的分析中我们已经提到了分摊成本,接下来我们就介绍一下平均分析与分摊分析:

平均复杂度或期望复杂度(average/expected complexity)是指根据数据结构各种操作出现概率的分布,将对应的成本加权平均。各种可能的操作,作为独立事件分别考察。割裂了操作之间的相关性和连贯性。往往不能准确地评判数据结构和算法的真实性能。

分摊复杂度(amortized complexity)是指对数据结构连续地实施足够多次操作,所需总体成本分摊至单次操作。从实际可行的角度,对一系列操作做整体的考量。更加忠实的刻画了可能出现的操作序列。更为精准的评判数据结构和算法的真实性能。

无序向量

首先是元素访问的问题,显然我们可以通过V.get(r)和V.put(r, e)接口读写向量元素,但就便捷性而言,远不如数组元素的下标访问方式:A[r],因此我们可以重载下标操作符“[]”,即:

此后,对外的V[r]即对应于内部的V._elem[r],它可以当左值也可以当右值使用,即:

左值:T x = V[r] + U[s] * W[t];

右值:V[r] = (T)(2*x+3);

其次是插入:

然后是区间删除:

接下来是单元素删除,显然它可以视作区间删除操作的特例,即[r] = [r, r+1):

那么,我们可不可以反过来,基于remove(r)接口,通过反复的调用,实现remove(lo, hi)呢?这是可以的,但是每次循环耗时正比于删除区间的后缀长度 = n-hi = O(n),而循环次数等于区间宽度 = hi-lo = O(n),如此,将导致总体O(n2)的复杂度。

前面我们介绍的都是无序向量的基本操作,接下来我们介绍无序向量的查找操作,首先是顺序查找

值得注意的是,此算法是一个输入敏感(input-sensitive)的算法,即最好情况下是O(1),而最坏情况下是O(n)。接下来我们讨论无序向量的去重操作,代码如下:

我们先分析其正确性,易见,凡被剔除者均为重复元素(不多),故只需证明,算法不致遗漏重复元素(不少)。不变性:在当前元素V[i]的前缀V[0, i)中,各元素彼此互异,初始i = 1时自然成立,后续的一般情况…;单调性:随着反复的while迭代,(1)、当前元素前缀的长度单调非降,且迟早增至_size(2)、当前元素后缀的长度单调下降,且迟早减至0。故算法必然终止,且至多迭代O(n)轮,其实(1)和(2)是相对应的,但(2)更易把握。现在我们再来分析其复杂度,每轮迭代中find()和remove()累计耗费线性时间,总体O(n2),显然这是可以进一步优化的,比如:(1)、仿照uniquify()高效版的思路,元素移动的次数可降至O(n),但比较次数依然是O(n2);(2)、先对需删除的重复元素做标记,然后再统一删除,稳定性保持,但因查找长度更长,从而导致更多的比对操作;(3)、V.sort().uniquify():简明实现最优的O(nlogn)。

最后我们介绍无序向量的遍历操作,

有序向量

我们先考察有序性及其甄别,与冒泡排序算法的理解相同:有序(无序)序列中,任意(总有)一对相邻元素顺序(逆序),因此,相邻逆序对的数目,可用以度量向量的逆序程度。即:

其实无序向量经预处理转换为有序向量之后,相关算法多可优化。前面我们介绍了无序向量的去重操作,即唯一化,那么对于有序向量的唯一化又该如何呢,它是否比无序向量的唯一化效率更高呢?我们来分析一下,不难发现,在有序向量中,重复的元素必然相互紧邻构成一个区间,因此,每一区间只需保留单个元素即可,如下面的算法:

分析此算法的复杂度:运行时间主要取决于while循环次数,共计:_size-1 = n-1,最坏情况下,每次都需调用remove(),各耗时O(n-1)~O(1),累计O(n2),尽管省去find(),总体竟与无序向量的deduplicate()相同,显然,这是一个低效算法,低效的根源在于,同一元素可作为被删除元素的后继多次前移,因此,若能以重复区间为单位,成批删除雷同元素,性能必将改进。那么就让我们来看一下下面的高效算法:

显然这个高效算法,共计n-1次迭代,每次常数时间,累计O(n)时间。

接下来我们介绍有序向量的查找算法,首先定义统一接口:

我们可以采用减而治之的思想,以任一元素x = S[mi]为界(其中S[mi]称作轴点),都可将待查找区间分为三部分,既然向量整体有序,则必有:S[lo, mi) <= S[mi] <= S(mi, hi),我们只需将目标元素e与x做一比较,即可分三种情况进一步处理:

  1. e < x:则e若存在必属于左侧子区间S[lo, mi),故可递归深入
  2. x < e:则e若存在必属于右侧子区间S(mi, hi),亦可递归深入
  3. e = x:已在此处命中,可随即返回

若轴点mi取做中点,则每经过至多两次比较,或者能够命中,或者将问题规模缩减一半。这就是二分查找

我们可以大致看出这是一个线性递归:T(n) = T(n/2) + O(1) = O(logn),大大优于顺序查找;运用递归跟踪可知:轴点总取中点,递归深度O(logn),各递归实例均耗时O(1)。如何更为精细的评估查找算法的性能呢?我们可以考察关键码的比较次数,即查找长度(search length),通常,需分别针对成功与失败查找,从最好、最坏、平均等角度评估,比如,成功、失败时的平均查找长度均大致为O(1.50logn)

我们前面所说的二分查找版本的效率仍有改进余地,因为不难发现转向左、右分支前的关键码比较次数不等,而递归深度却相同,若能通过递归深度的不均衡,对转向成本的不均衡进行补偿,平均查找长度应能进一步缩短。比如,若设n = fib(k) – 1,则可取mi = fib(k-1) – 1,于是,前、后子向量的长度分别为fib(k-1) – 1、fib(k-2) – 1,这就是Fibonacci查找

Fibonacci查找的ASL,(在常系数的意义上)优于二分查找。

换一种角度看问题,二分查找中左、右分支转向代价不平衡的问题,也可直接解决。比如,每次迭代(或每个递归实例)仅作一次关键码比较,如此,所有分支只有2个方向,而不再是3个。同样的,轴点mi取做中点,则查找每深入一层,问题规模也缩减一半:

  1. e < x:则e若存在必属于左侧子区间S[lo, mi),故可递归深入
  2. x <= e:则e若存在必属于右侧子区间S[mi, hi),亦可递归深入

只有当元素数目hi-lo=1时,才判断该元素是否命中,代码如下:

最后再来看一种插值查找的算法,我们假设已知有序向量中各元素随机分布的规律,比如均匀且独立的随机分布,于是,[lo, hi)内各元素应大致按照线性增长趋势,即(mi-lo)/(hi-lo) ≈ (e-A[lo])/(A[hi]-A[lo]),因此通过猜测轴点mi,可以极大地提高收敛速度,即mi ≈ lo+(hi-lo)*(e-A[lo])/(A[hi]-A[lo])。我们查字典通常就是按照这种方法查找的。

冒泡排序

回忆我们之前提到的冒泡排序:

我们对这个算法再改进,可以得到下面这个算法:

这个算法的效率与我们之前提到的冒泡算法的效率相比,是相同的,即在最好的情况下是O(n),最坏的情况下是O(n2)。那么我们改进它的目的是什么呢?当输入含重复元素时,算法的稳定性(stability)是更为细致的要求。稳定性通常指重复元素在输入、输出序列中的相对次序是否保持不变。显然,我们这个改进算法的稳定性确实更好。在冒泡排序中,元素a和b的相对位置发生变化,只有一种可能:经分别与其他元素的交换,二者相互接近直至相邻;在接下来一轮扫描交换中,二者因逆序而交换位置。

归并排序

归并排序是采用分而治之的策略,即把序列一分为二(O(1)),对子序列递归排序(2*T(n/2)),最后合并有序子序列(O(n))。若真能如此,整体的运行成本应该是O(nlogn)。代码如下:

显然此算法的重点在于归并算法,将两个有序序列合并为一个有序序列,我们称之为二路归并(2-way merge),即S[lo, hi) = S[lo, mi) + S[mi, hi)。它的基本实现如下:

精简实现如下:

接下来我们主要分析其复杂度,显然算法的运行时间主要消耗于for循环,共有两个控制变量,初始时:j = 0,k = 0;最终时:j = lb,k = lc;亦即:j + k = lb + lc = hi – lo = n。通过观察可知,每经过一次迭代,j和k中至少有一个会加一(j+k也必至少加一),故可知,merge()总体迭代不过O(n)次,累计只需线性时间。这一结论与排序算法的Ω(nlogn)下界并不矛盾,毕竟这里的B和C均已各自有序。注意,待归并子序列不必等长,亦即,允许lb != lc,mi != (lo+hi)/2。实际上,这一算法及结论也适用于另一类序列,即列表。综合评价,归并算法的优点:实现最坏情况下最优O(nlogn)性能的第一个排序算法;不需随机读写,完全顺序访问,尤其适用于列表之类的序列、磁带之类的设备;只要实现恰当,可保证稳定,出现雷同元素时,左侧子向量优先;可扩展性极佳,十分适宜于外部排序,海量网页搜索结果的归并;易于并行化。缺点:非就地,需要对等规模的辅助空间;即便输入完全(或接近)有序,仍需Θ(nlogn)时间。



发表评论

电子邮件地址不会被公开。 必填项已用*标注