ASL吐血整理&&数据结构查找 |
您所在的位置:网站首页 › 数据结构什么是查找 › ASL吐血整理&&数据结构查找 |
ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数成为平均查找长度。
其中 (一些概念补充(不那么重要): 查找表:同一类数据元素(或记录)所构成的集合。 关键字:是数据元素(或记录)中某个数据项的值,用他可以标识一个数据元素(或记录),若此关键字可以唯一的标识一个,称 为主关键字0。反之,若可以识别若干称为次关键字。 动态查找链表,静态查找链表:若在查找的同时对表修改操作(删除,插入等),称为动态链表。反之,静态链表。) 线性表查找:时间复杂度O(n) 1.查找成功: 分析: 查找方式为从头扫到尾,找到待查找元素即查找成功,若到尾部没有找到,说明查找失败。所以说,Ci(第i个元素 的比较次数)在于这个元素在查找表中的位置,如第0号元素就需要比较一次,第一号元素比较2次......第n号元素要 比较n+1次。所以Ci=i。 2.查找失败: 分析:当待查找元素不在查找表中时,也就是扫描整个表都没有找到,即比较了n次,查找失败 3.适用情形:算法简单,对查找表结构无任何要求,有序与否都行 n太大时,查找效率低。 折半查找:时间复杂度O( 待查找表是有序表,这是折半查找的要求。在折半查找中,用二叉树描述查找过程,查找区间中间位置作为根,左子表为左子树,右子表为右子树,因此这颗树也被成为判定树(decision tree)或比较树(Comparison tree)。查找方式为,先与树根结点进行比较,若k小于根,则转向左子树继续比较,若k大于根,则转向右子树,递归进行上述过程,直到查找成功或查找失败。k是关键字。 1.查找成功: 分析:折半查找也称二分查找,成功的折半查找恰好是走了一条从判定树根到被查节点的路径,比较关键字个数恰为该结点在 树中的层数,具有n个结点的判定树的深度为[ 假设判定树结点个数是n= 例如:
2.查找失败: 共12个空节点,而查找每个记录为空概率是 方格结点是失败的结点,本身不存在,不需要比较到他自己,只需要比较到他的父节点即可,因此为3*4; (eg:要在树中查找1,只用依次搜索25,10,2就行了,发现比2小就不要找了,因为已经知道2没有左子树,总共比较了3次。) 3.适用情形:比较次数少,查找效率高,只用于顺序存储的有序表,不适用于经常修改操作(删除插入等)。 分块查找:时间复杂度为O(log₂(m)+N/m),m为分块的数量,N为主表元素的数量,N/m 就是每块内元素的数量 在原表的基础上建立一个分块有序表(也称子表方便我后面描述)(每个分块都输有序的,第二个分块的记录大于第一个分块记录)。每个子表包含两个,一是关键字项(该字表内最大的关键字),二为指针项(子表中第一个记录的位置)。 先确定待查记录所在的块,然后在块中按顺序查找或折半查找(子表中的记录可能任意排列)。 1.查找成功:
将长度为n的表均匀的分为b块,每块含有s个记录,b=n/s; 所以在总块中查找的概率是1/b;分块中每个记录查找的概率是1/s; 分块用顺序表 分块用折半查找 2.适用情形 可以快速进行修改操作,块内可以无序,缺点就是新增一个索引表。 如有错误,请联系我。谢谢你可以让我及时发现! |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |