查找算法的分析及应用
标签: 数据结构
学习人数: 5765


全屏播放
赞赏支持

本章我们学了一下几种查找方法

 

内部查找

一般对于内存中一个序列的数字集合的查找,我们采用下面几种查找方式

顺序查找,时间复杂度O(N),
分块查找,时间复杂度O(logN+N/m);
折半查找,时间复杂度O(logN)
哈希查找,时间复杂度O(1)

 

外部查找

我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比二叉查找树还小吗?
答案当然不是,B树和B+树的出现是因为另外一个问题,那就是磁盘IO;众所周知,IO操作的效率很低,那么,当在大量数据存储中,查询时我们不能一下子将所有数据加载到内存中,只能逐一加载磁盘页,每个磁盘页对应树的节点。造成大量磁盘IO操作(最坏情况下为树的高度)。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。
所以,我们为了减少...

登录查看完整内容


课后作业

课后习题

 

【2016年真题】在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。

k = 0;  
while (k < n 且 A[k] < x) k = k + 3;  
if (k < n 且 A[k] == x)查找成功;  
else if (k-1 < n 且 A[k-1] == x)查找成功;  
else if (k-2 < n 且 A[k-2] == x)查找成功;  
else 查找失败;  

本算法与折半查找算法相比,有可能具有更少比较次数的情形是()
A.当x不在数组中            B.当x接近数组开头处
C.当x接近数组结尾处        D.当x位于数组中间位置

参考答案:B

 

【2013年真题】设包含 4 个数据元素的集合 S={ "do","for"," repeat"," while"},各元素的查找概率依次为:p1=0.35,p2 = 0.15,p3=0. 15,p4=0.35。将 S 保存在一个长度为 4 的顺序表中,采用折半查找法,查找成功时的平均查找长度为 2.2。请回答: 
(1)若采用顺序存储结构保存 S,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少? 
(2)若采用链式存储结构保存 S,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?

参考答案:
(1)采用顺序存储结构,数据元素按其查找概率降序排列。
采用顺序查找方法。
查找成功时的平均查找长度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。
(2)
【答案一】 
采用链式存储结构,数据元素按其查找概率降序排列,构成单链表。 
采用顺序查找方法。
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
【答案二】 
采用二叉链表存储结构,构造二叉排序树,元素存储方式见下图。

采用二叉排序树的查找方法。
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。


【2011年真题】一个长度为 L(L≥1)的升序序列 S,处在第L/2个位置的数称为 S 的中位数。 例如,若序列 S1=(11,13,15,17,19),则 S1 的中位数是 15,两个序列的中位数是含它 们所有元素的升序序列的中位数。例如,若 S2=(2,4,6,8,20),则 S1 和 S2 的中位数是 11。现在有两个等长升序序列 A 和 B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列 A 和 B 的中位数。要求: 
(1)给出算法的基本设计思想。 
(2)根据设计思想,采用 C 或 C++或 JAVA 语言描述算法,关键之处给出注释。 
(3)说明你所设计算法的时间复杂度和空间复杂度。 

解答: 
(1)算法的基本设计思想如下。 
分别求出序列 A 和 B 的中位数,设为 a 和 b,求序列 A 和 B 的中位数过程如下: 
1)若 a=b,则 a 或 b 即为所求中位数,算法结束。 
2)若 a<b,则舍弃序列 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求舍弃的长度相等; 
3)若 a>b,则舍弃序列 A 中较大的一半,同时舍弃序列 B 中较小的一半,要求舍弃的长度相等; 
在保留的两个升序序列中,重复过程 1)、2)、3),直到两个序列中只含一个元素时为止,较小者即为所求的中位数。 
(2)算法的实现如下: 

int M_Search(int A[],int B[],int n){  
    int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2;  
    //分别表示序列 A 和 B 的首位数、末位数和中位数  
    while(s1!=d1||s2!=d2){  
        m1=(s1+d1)/2;  
        m2=(s2+d2)/2;  
        if(A[m1]==B[m2])   
            return A[m1]; //满足条件 1)  
        if(A[m1]<B[m2]){ //满足条件 2)  
            if((s1+d1)%2==0) { //若元素个数为奇数  
                s1=m1; //舍弃 A 中间点以前的部分且保留中间点  
                d2=m2; //舍弃 B 中间点以后的部分且保留中间点  
            }  
            else{ //元素个数为偶数  
                s1=m1+1; //舍弃 A 中间点及中间点以前部分  
                d2=m2; //舍弃 B 中间点以后部分且保留中间点  
            }   
        }  
        else{ //满足条件 3)  
            if((s1+d1)%2==0) { //若元素个数为奇数  
                d1=m1; //舍弃 A 中间点以后的部分且保留中间点  
                s2=m2; //舍弃 B 中间点以前的部分且保留中间点  
            }  
            else{ //元素个数为偶数  
                d1=m1+1; //舍弃 A 中间点以后部分且保留中间点  
                s2=m2; //舍弃 B 中间点及中间点以前部分  
            }   
        }   
    }  
    return A[s1]<B[s2]? A[s1]:B[s2];  
}  

(3)算法的时间复杂度为 O(log2n),空间复杂度为 O(1)。 


登录后发布评论

暂无评论,来抢沙发