算法之数字查找

基础的数字查找算法分为两种:基于比较的查找、基于HASH的查找。本节主要回顾基于比较的查找,重点理解其算法思想、与实现过程中的方法。

基于比较的查找,即要求查找集合中元素间具有某种关系,才有查找算法可言。若是元素随机排列,那只能是挨个查看的算法,当然也可以加速“挨个查看”的速度,如划分子集,然后并行查找。

最值查找

集合中存在两个最值:最小值与最大值。找其中一个最值,如果说集合中元素间存在有序关系,那么可以直接利用此先验条件给出;如果没有任何先验条件,那么只能在 Θ(n)的时间内找到。《算法导论》中一个比较有意思的算法:同时(simultaneous)找到最大值与最小值,一个比较优的复杂度算法。

看到这个算法,再次联想到在这篇博文中提到的信息论理论。即其并非直观地取集合中每个元素与最值进行比较,以确定最值是否更换;而是取集合中两个元素进行比较,比较结果中的较大元素与已知最大值比较,较小元素与已知最小值比较。直观来看,原始的比较方法,两个元素需要4次比较才能确定最值,而采取较优的方法后,只需3次。即一个|A| = n的集合,能在3*n/2次比较完成最值求解。

中值查找

这里的中值是一个泛化的概念,即为集合中第i大的数字,即满足集合中有且仅有i-1个数字不大于此数字。中值查找在平均的情况下,可以在Θ(n)的时间复杂度下完成,这主要得益于快排中的PARTITION算法。其中为了避免有序集合对PARTITION算法的干扰,需要使用随机选择PIVOT版本完成,以保证出现以每次单个元素趋近中值的概率最低。

《算法导论》给出了一个在最坏情况下,时间复杂度为Θ(n)的中值查找算法。简单再说就是:

  1. 对集合进行划分,每个子集包含5个元素,最后一个子集元素个数为|A|%5   -  Θ(n)
  2. 利用插入等比较排序算法,对每个子集排序,然后直接取到“真中值”    -  Θ(n)
  3. 对2中,取出的中值,构成新的集合,若新集合元素个数大于5,递归执行1,2;直至元素个数小于5,取得整个集合的中值x     -  T(n/5)+Θ(n)
  4. 利用“真中值”x,采用PARTITION算法,对集合进行切分,得到划分后新集合B   -   Θ(n)
  5. 若“真中值”x在新集合B中的索引k为所求的第i大值,则返回索引k;若k>i,则返回1步对集合B[0 : k) 寻找第i大的值;若k<i,则返回1步 对集合B(k:n) 寻找第i-k+1大的值  -  T(7n/10) +Θ(n)

这个算法,很容易理解。即通过一种更为主动的方式寻找集合真正的中值来切分集合,如同下面的二分查找一样,每次都能将解缩小一半的规模。问题在于,在算法中的 第1步中,为什么一定要用取5个元素,取3,7,9(只能取奇数,这样便于取得“真中值”)行不行?经过查询网上资料,发现取3,7都会使算法的复杂度下界高于Θ(n)。

此算法复杂度(下界或最差)分析,其中第1,2,3,4步可直观得到,第5步是以x分隔集合为两个集合,其中一个作为子问题的集合继续参与计算。我们要寻找最差情况(不太好找),那么可以找出其补集。假设要寻找中值左侧(即小于中值的元素集),前面我们知道,总共有⌈n/5⌉个分组,可以确定的是有⌈⌈n/5⌉/2⌉个分组属于为大于中值的分组,且这⌈⌈n/5⌉/2⌉中,至少每个分组要“贡献”3个大于x的元素,因此在最理想(希望补集越大越好)的情况下,补集规模为⌈⌈n/5⌉/2⌉*3(见下图阴影部分)因此,反之,在最差的情况下,子问题的解为 n-⌈⌈n/5⌉/2⌉,即⌈7n/10⌉,这样就有了,该算法的时间复杂度下界为:

T(n) = T(⌈n/5⌉) + T(⌈7n/10⌉) + 5 O(n)

SELECT算法时间复杂度分析

二分查找

集合中元素位于线性结构中且相邻元素存在有序关系,那么可以应用二分查找,类似于快速排序中的思想。即将集合切分,缩小解空间。这里联想到这篇博文,即只有那些将问题等概率切分的算法,才能得到较优的时间复杂度。而二分查找,正是利用了相邻有序这一先验条件,每次确定都会对解进行等概率切分。或者可以说,那些对待问题时不抱有任何可能性幻想,而是对将要面对的问题空间以等概率分布(最大熵原理)来对待,才能避免被“问题”钻空子。

二分查找算法与计算机结合时,就会遇到因存储结构不同而面临不同的问题,毕竟计算是在计算机内的存储体上展开。如果存储体依序存放在随机可访问的线性表中,那么与算法原始的假设是一致。二分查找算法与非线性表,如树,结合在一起,就演化出具有查找功能的查找树。

简单查找树

具备自动调整平衡的AVL树、红黑树将在后面的高级数据结构体分析。这里重点回忆和提炼简单二分查找树的一些内在特性。

一想到二分查找树,就联想到分形算法生成的分形图形,即部分与总体具备同样的结构,用计算语言就是可递归表达。二分查找树,从本质上讲是把二分查找算法用数据结构表达出来,即每次比较,都尽可能(只所以是尽可能,是考虑到树的平衡性)地将问题规模缩小为原来的一半,这样便符合上面说的不让问题“钻空子”,以实现高效的查找。

有一棵二分树,将其放入一个二维数组中,其中需要满足任何一棵子树,其根坐标为(i,j),则左子树根为(i+1,j-k),右子树根为(i+1,j+k),i,j,k∈正整数

  1. 假设树是满树,若树深度为h,那么二维数组的维数最少为多少?
  2. 假设树是满树,如何遍历树以将其各个结点的下标输出?
  3. 假设树不是满树,如何遍历树以将其各个结点的下标输出?

原以为这个问题采用如下的递归,就可以得出,即以树根为原点(0,0):
Vist(Node,i,j)

  1. if Node not NULL
  2.     Visit(Node->left, i--,j++)
  3.      print (i,j)
  4.      Visit(Node->right,i++,j++)

实际这个问题没有意识到树的增长是指数级,而不是常数级倍数增长。如果说,一棵树的所有节点能放入一个方格,且任意子树之间都相差固定的距离,那么树的增长就是常数倍增长。

结构化数据,尤其元素间具备相互关系的结构化数据,可以将算法固化在数据结构中加速数据计算,但同时其带来的就是由于算法的固化,导致数据修改后需要进行复杂的调整以保持固有的元素间关系。这从简单查找树在建立完毕后,进行查找时,可以自发地使用二分查找算法;同时在添加、修改和删除树中节点时,面临着平衡调整、树局部及至整体调整的问题。下面以树中节点删除为例说明固化有算法的结构在关系破坏后重建的艰难。

节点删除后,重建二分树,实际上重建的是元素间的关系。而二分查找树的关系是;Root >== Left-Tree && Root<=Right-Tree。其实如果将这个固化在二叉树中的递归算法“摊平”,就是快排中的Partition算法,即根为第一次Partition选出的pivot,左树为第一次Partition划归到左边元素集,右树为第一次Partition划归到右边元素集,依次类推。也就是二分查找树存在一种内在的线性有序,其中在有序集中的最值满足:任意树的最左叶子必然是整棵树最小元素,且任意树的最右叶子必然是整棵树最大元素。现在要删除一个节点:

  1. 如果节点是一个叶子,并未破坏已有元素间的关系
  2. 如果节点是一棵树的根,只要将右子树挂到左子树的最右叶子,作为其右子树;或者将左子树挂到右子树的左叶子,作为其左子树即可

其中2的原理就来自于二分查找树其固化的算法。当然,重建是为了后续更好地使用(即使用固化算法),因此重建相当于对快排,重新选择一次partition的pivot,而这极有可能导致新的partition不够平衡以至“固化算法”向线性查找退化。所以在重建完成后,虽然元素间关系得到满足,但还需要调整结构,以使“固化算法”最优,这就是后面要说的AVL树。

发表评论