常用的查找算法PPT.ppt

单击此处编辑母版标题样式,2,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,查找算法,1,2,1.,顺序查找,2.,二分查找,3.,插值查找,4.,树表查找,5.,哈希查找,常用查找算法,2,2025/4/29 周二,说明：,顺序查找适合于存储结构为顺序存储或链接存储的线性表。,基本思想：,顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值,k,相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于,k,的结点，表示查找失败。,复杂度分析：,查找成功时的平均查找长度为：（假设每个数据元素的概率相等）,ASL=1/n(1+2+3+n)=(n+1)/2;,当查找不成功时，需要,n+1,次比较，时间复杂度为,O(n);,顺序查找,3,2025/4/29 周二,说明：,元素必须是有序的，如果是无序的则要先进行排序操作。,基本思想：,也称为是折半查找，属于有序查找算法。用给定值,k,先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据,k,与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。,复杂度分析：,最坏情况下，关键词比较次数为,log,2,(n+1),，且期望时间复杂度为,O(log2n),；,二分查找,4,2025/4/29 周二,注意事项：,折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。,二分查找,5,2025/4/29 周二,在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？,打个比方，在英文字典里面查“,apple”,，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“,zoo”,，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。,2,；,2.根结点的儿子数为,2,M,；,3.,除根结点以外的非叶子结点的儿子数为,M/2,M,；,4.,每个结点存放至少,M/2-1,（取上整）和至多,M-1,个关键字；（至少,2,个关键字）,5.,非叶子结点的关键字个数,=,指向儿子的指针个数,-1,；,6.,非叶子结点的关键字：,K1,K2,KM-1,；且,Ki Ki+1,；,7.,非叶子结点的指针：,P1,P2,PM,；其中,P1,指向关键字小于,K1,的子树，,PM,指向关键字大于,KM-1,的子树，其它,Pi,指向关键字属于,(Ki-1,Ki),的子树；,8.,所有叶子结点位于同一层；,树表查找,11,2025/4/29 周二,树表查找,12,2025/4/29 周二,树表查找,13,2025/4/29 周二,树表查找,14,2025/4/29 周二,树表查找,15,2025/4/29 周二,树表查找,16,2025/4/29 周二,3.B+,树,B+,树是,B-,树的变体，也是一种多路搜索树：,1.,其定义基本与,B-,树同，除了：,2.,非叶子结点的子树指针与关键字个数相同；,3.,非叶子结点的子树指针,Pi,，指向关键字值属于,Ki,Ki+1),的子树,4.,为所有叶子结点增加一个链指针；,5.,所有关键字都在叶子结点出现；,树表查找,17,2025/4/29 周二,树表查找,18,2025/4/29 周二,B,和,B+,树的区别在于，,B+,树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。,B+,树的优点在于：,由于,B+,树在内部节点上不好含数据信息，因此在内存页中能够存放更多的,key,。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。,B+,树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而,B,树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有,B+,树好。,B+,树更适合做文件系统。,但是,B,树也有优点，其优点在于，由于,B,树的每一个节点都包含,key,和,value,，因此经常访问的元素可能离根节点更近，因此访问也更迅速。,树表查找,19,2025/4/29 周二,B-/B+,树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少,IO,操作。它广泛用于文件系统及数据库中，如：,Windows,：,HPFS,文件系统；,Mac,：,HFS,，,HFS+,文件系统；,Linux,：,ResiserFS,，,XFS,，,Ext3FS,，,JFS,文件系统；,数据库：,ORACLE,，,MYSQL,，,SQLSERVER,等中。,树表查找,20,2025/4/29 周二,什么是哈希表（,Hash,）？,我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素,分类,，然后将这个元素存储在相应,类,所对应的地方。,在此，我们按这个思想建立的表就成为哈希表。,哈希查找,21,2025/4/29 周二,哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。,常见的几种哈希函数：,1.,直接定址法,取关键字或关键字的某个线性函数值为哈希地址,H(key)=key,或,H(key)=a*key+b,2.,除留余数法,取关键字被某个不大于哈希表表长,m,的数,p,除后所得余数的哈希地址。,H(key)=key mode p p=m,哈希查找,22,2025/4/29 周二,算法思想：,哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。,算法流程：,1,）用给定的哈希函数构造哈希表；,2,）根据选择的冲突处理方法解决地址冲突；,常见的解决冲突的方法：拉链法和线性探测法。,3,）在哈希表的基础上执行哈希查找。,哈希查找,23,2025/4/29 周二,我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是,map,，也就是我们常说的,KV pair,，经常使用,Python,的博友可能更有这种体会。使用,map,的好处就是，我们在后续处理数据处理时，可以根据数据的,key,快速的查找到对应的,value,值。,map,的本质就是,Hash,表，那我们在获取了超高查找效率的基础上，我们付出了什么？,哈希查找,24,2025/4/29 周二,Hash,是一种典型,以空间换时间,的算法，比如原来一个长度为,100,的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是,byte,类型数据，那么该数组占用,100byte,空间。现在我们采用,Hash,算法，我们前面说的,Hash,必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的,hash,表，此时，仍然是,100byte,的数组，假设我们需要的,100byte,用来记录键与位置的关系，那么总的空间为,200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。,哈希查找,25,2025/4/29 周二,