平均查找长度 订阅
为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(),ASL成功。 展开全文
为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(),ASL成功。
信息
外文名
Average Search Length
简    称
ASL
其    他
不详
中文名
平均查找长度
工资工资定义
为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(),ASL成功。对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中:Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数。在查找表中查找不到待查元素,但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度,不成功。
收起全文
精华内容
参与话题
问答
  • 关于平均查找长度 ASL 可以建一颗二叉树,解决一些对数列进行二分查找的问题 eg: 对有序数组 5 13 19 21 37 56 64 75 88 92 100 进行二分查找,等概率的情况下,查找成功的**平均查找长度(平均比较次数)**是??? ...

    关于平均查找长度 ASL
    可以建一颗二叉树,解决一些对数列进行二分查找的问题
    eg:
    对有序数组
    5 13 19 21 37 56 64 75 88 92 100
    进行二分查找,等概率的情况下,查找成功的**平均查找长度(平均比较次数)**是???

    可以建一颗二叉树
    (本垃圾手绘图片)
    在这里插入图片描述
    鸭鸭鸭
    观察一下,每次进行二分建树
    这很好理解对吧

    然后,重点来了
    公式拿来,这个不良心的博主
    公示不给

    平均查找长度 ASL=查找次数和/树的节点总个数
    eg:
    本题的答案:

    (1*1+2*2+3*4+4*4)/11=33/11;
    

    可以发现背公式得
    平均查找长度和每层的深度和在此深度上的节点个数有关!!!!!!
    剩下的就自己去悟吧
    其实是博主也不是很会
    可以去搜些资料

    谢谢阅读

    展开全文
  • 一、链地址法在等概率下查找成功和查找不成功的平均查找长度:将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功...

    一、链地址法在等概率下查找成功和查找不成功的平均查找长度:

    题目

    将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功的平均查找长度

    1mod11=1,所以数据1是属于地址1
    13mod11=2,所以数据13是属于地址2
    12mod11=1,所以数据12也是属于地址1(这个数据是数据1指针的另一个新数据)
    34mod11=1,所以数据34是属于地址1(这个数据是数据12指针的另一个新数据)
    38mod11=5,所以数据38是属于地址5
    33mod11=0,所以数据33是属于地址0
    27mod11=5,所以数据27是属于地址5,(这个数据是数据38指针的另一个新数据)
    22mod11=0,所以数据22是属于地址0,(这个数据是数据33指针的另一个新数据)

    链地址法处理冲突构造所得的哈希表如下:
    链地址法

    查找成功时: ASL=(3×1+2×3+1×4)/8=13/8, 其中红色标记为查找次数。也就是说,需查找1次找到的有4个,其它以此类推…

    查找不成功时:ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11;或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11,其中红色标记为查找次数。以第一个3为例,其对应于0地址位,确定查找不成功需比较3次,其它以此类推…

    原理:

    链地址法插入数据的时候采用采用头插法(插入每个链表的表头),因为习惯默认新插入进来的数据,马上就要访问到。下边是实现的伪代码

    CHAINED-HASH-INSERT(T, x)
        insert x at the head of list T[h(key[x])]
    CHAINED-HASH-SEARCH(T, k)
        search for an element with key k in list T[h(k)]
    CHAINED-HASH-DELETE(T, x)
         delete x from the list T[h(key[x])]
    
    例子

    例如,查找16的时候,根据散列函数在地址为5的链表查找,首先找到27,再找到38,然后找到38的后继节点为空,查找结束。查找结果失败,共查找3次。

    二,线性探测再散列法处理冲突

    对于这部分,个人觉得有人整理的比较好,很有条理,很清晰,可以借鉴一下,链接如下:
    线性探测再散列法处理冲突

    展开全文
  • 数据结构---平均查找长度ASL的相关计算技巧

    万次阅读 多人点赞 2017-11-19 22:51:49
    个人总结的有关考研数据结构中平均查找长度ASL的三种计算小技巧:1.顺序查找法的平均查找长度为:(n+1)/2 2.散列表的查找成功和查找不成功的平均查找长度 技巧(线性探测法和链地址法): ① 查找成功时的比较...

    个人总结的有关考研数据结构中平均查找长度ASL的三种计算小技巧:

    1. 顺序查找法的平均查找长度为:(n+1)/2
    2. 散列表的查找成功和查找不成功的平均查找长度
      技巧(线性探测法和链地址法):
      ① 查找成功时的比较次数是基于关键字计算的;查找不成功时的比较次数是基于Hash函数计算得到的地址计算的。
      ②查找成功的计算只有一种情况;查找不成功的计算有两种情况,关键是看题目中是否含有(只将与关键字的比较计算在内)
      若没有,查找过程中遇到空位置,则证明查找失败;若有,则查找过程中只需比较关键字即可。
     注意:①查找成功是除关键字的个数;②查找不成功是除mod后的数值
    
    1. 折半查找成功和查找不成功的平均查找长度:

      以折半查找的方式,将逐个查找出来的数值建立判定树,根据判定树求查找成功和查找不成功的平均查找长度。

    注意:①查找成功是除关键字个数;②查找不成功是除关键字个数加1
    

    个人的理解就是这样,希望能够帮到部分同在考研的研友们!

    展开全文
  • Hash表的平均查找长度ASL计算方法

    万次阅读 多人点赞 2016-09-23 21:30:05
    Hash表的“查找成功的ASL”和“查找不成功的ASL” 鉴于网络上流传了各种计算方法,有的甚至错误百出。本人感觉此种计算方法比较合理,故采纳之。特著此文,以备查阅,欢迎交流。

    Hash表的“查找成功的ASL”和“查找不成功的ASL”

    ASL指的是 平均查找时间

    关键字序列:(7、8、30、11、18、9、14)

    散列函数:
    H(Key) = (key x 3) MOD 7

    装载因子:
    0.7

    处理冲突:线性探测再散列法


    查找成功的ASL计算方法:

    因为现在的数据是7个,填充因子是0.7。所以数组大小=7/0.7=10,即写出来的散列表大小为10,下标从0~9。
    第一个元素7,带入散列函数,计算得0。
    第二个元素8,带入散列函数,计算得3。
    第三个元素30,带入散列函数,计算得6。
    第四个元素11,带入散列函数,计算得5。
    第五个元素18,带入散列函数,计算得5;此时和11冲突,使用线性探测法,得7。
    第六个元素9,带入散列函数,计算得6;此时和30冲突,使用线性探测法,得8。
    第七个元素14,带入散列函数,计算得0;此时和7冲突,使用线性探测法,得1。
    所以散列表

    地址 0 1 2 3 4 5 6 7 8 9
    key 7 14 8 11 30 18 9

    所以查找成功的计算:
    如果查找7,则需要查找1次。
    如果查找8,则需要查找1次。
    如果查找30,则需要查找1次。
    如果查找11,则需要查找1次。
    如果查找18,则需要查找3次:第一次查找地址5,第二次查找地址6,第三次查找地址7,查找成功。
    如果查找9,则需要查找3次:第一次查找地址6,第二次查找地址7,第三次查找地址8,查找成功。
    如果查找地址14,则需要查找2次:第一次查找地址0,第二次查找地址1,查找成功。
    所以,ASL=(1+2+1+1+1+3+3)/ 7=12/ 7


    查找不成功的ASL计算方法:

    鉴于网络上有各种版本,本人认为此种计算方法比较合理。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案。

    1. 定义什么叫查找不成功
    举个例子来说吧。在已知上面散列表的基础上,如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字,发现key=11,不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为6的值,发现key=30,依然不等。这个时候到了地址为6,但是依然没有找到。那么就说明根本就没有key=4这个关键字,说明本次查找不成功。注意:为什么到地址6?因为散列函数中有 mod7 ,对应的地址为0~6,即0~6查找失败的查找次数。
    再举一个例子。查找key为0的关键字,根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字,发现key=7,不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为1的值,发现key=14,依然不等。这个时候到了地址为3,发现为空依然没有找到。所以停止查找,本次查找不成功。因为如果key=0这个关键字存在的话,依照冲突处理函数,就一定能找到它。总不能丢了吧。

    2. 根据第一点定义的不成功,依次推下去:
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为2,
    查找地址为2的值所需要的次数为1,
    查找地址为3的值所需要的次数为2,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为5,
    查找地址为6的值所需要的次数为4。
    3.计算
    查找不成功ASL=(3+2+1+2+1+5+4)/ 7=18/ 7

    展开全文
  • ASL 指的是平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子: 0.7 处理冲突: 线性探测再散列法 查找成功的 ASL 计算方法: 因为现在的数据是 7 个,填充因子...
  • ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。 它的定义是这样的: 其中n为查找表中元素个数,Pi为...
  • ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数:  H(Key) = (key x 3) MOD 7 装载因子:  0.7 处理冲突:线性探测再散列法 查找成功的ASL计算方法: 因为现在的数据是7个,填充...
  • #include<stdio.h> #include<stdlib.h> #include<time.h> struct TreeNode { int Data; int Height; struct TreeNode * Left; struct TreeNode * Right; }; struct AVLNode{ ...
  • 平均查找长度ASL

    2019-10-18 23:15:27
    平均查找长度 是为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值。(Average Search Length,ASL) 百科的概念有些难懂,这里的长度其实不是一个具体的长度,而是衡量一个算法时间性能的数...
  • ASL 平均查找长度

    千次阅读 2018-09-04 08:40:12
    接下来整理一下上面每个方式的平均查找长度 顺序表查找ASL 如果每个关键字查找概率相同,则ASL = (n+1)/2。  一般都是概率相同。 二分查找ASL 举例说明: 这是一个有序序列(下标和关键字相同): 0 1 2 3 4 ...
  • ASL = 1/n * (每个查找元素深度之和) OK,举个例子: 深度为1的25的一个元素; 深度为2的10和30的两个个元素; 深度为3的2、15、28、35的四个元素; 深度为4的3、20、29、40的四个元素; ...
  •   hash 表在处理 collision 的时候有...  本文记录使用开链法的情况下,Hash 表查找成功和查找不成功的平均查找长度ASL - ),其他方法同理。   首先开链法是指,每一个表格元素维护一个list,hash function...
  • 有序线性表查找平均长度 ...长度为10的表,采用顺序查找法,平均查找长度ASL是? 如果一定可以找到的: 则10个数,每个被找到的概率是1/10; 每个元素被找到的长度分别是:1,2,3,。。,10; ASL=(1+2+3+。。+10...
  • 成功的ASL很简单,就是首先确定你要找的那个值,然后用hash进行查找计算,如果直接找到就是1次,如果hash(不一定就是原来的hash)的计算不止一次,就按你找到总共的次数计入。然后再套用公式计算就可以了,公式如下...
  • 关于ASL(平均查找长度)的简单总结

    千次阅读 多人点赞 2019-01-08 15:42:00
    ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数成为平均查找长度。 它的定义是这样的: 其中n为查找表中元素个数,Pi...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合   { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 ...
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...
  • 一、线性探测再散列法 Hash表: 元素的值(value)和在数组中索引位置(index)有一个确定关系 Index = Hash(key) ==&gt; y = f(x) Index有可能相同,怎么处理冲突?不同的老师、教材在“处理冲突”上可能会有不同的...
  • ASL=(1,2,3,4,5)/5=3 按关键字3,1,2,5,4构造而得的二叉排序树 ASL=(1+2+2+3+3)/5=2.2 很明显第二种序列的ASL要快。至于二叉排序树怎么构成的其实就是根据它的性质(若它的左子树不空,则左子树上所有结点的值均...
  • 平均查找长度

    千次阅读 2017-06-21 21:05:01
    平均查找长度ASL (Average Search Length)定义为:  ①n是结点的个数; ②Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即 pl=p2…=pn=1/n ③ci是找到第i个结点所需进行的比较次数。 ...
  • 查找——平均查找长度

    千次阅读 多人点赞 2017-06-19 11:14:36
    接下来整理一下上面每个方式的平均查找长度顺序表查找ASL如果每个关键字查找概率相同,则ASL = (n+1)/2。 一般都是概率相同。二分查找ASL举例说明:这是一个有序序列(下标和关键字相同): 0 1 2 3 4 初始化:low = ...

空空如也

1 2 3 4 5 ... 20
收藏数 3,003
精华内容 1,201
关键字:

平均查找长度