精华内容
下载资源
问答
  • 关于平均查找长度 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;
    

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

    谢谢阅读

    展开全文
  • ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。 它的定义是这样的: 其中n为查找表中元素个数,Pi为...

    平均查找长度

    ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

    它的定义是这样的:在这里插入图片描述

    其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。

    顺序查找平均查找长度的计算

    在顺序查找(Sequence Search)表中,查找方式为从头扫到尾,找到待查找元素即查找成功,若到尾部没有找到,说明查找失败。

    所以说,Ci(第i个元素的比较次数)在于这个元素在查找表中的位置,如第0号元素就需要比较一次,第一号元素比较2次…第n号元素要比较n+1次。所以Ci=i;所以

    查找成功 的平均查找长度:

    在这里插入图片描述

    查找失败 的平均查找长度:
    在这里插入图片描述

    折半查找平均查找长度的计算

    折半查找(Binary Search),首先待查找表是有序表,这是折半查找的要求。在折半查找中,用二叉树描述查找过程,查找区间中间位置作为根,左子表为左子树,右子表为右子树,因为这颗树也被成为判定树(decision tree)或比较树(Comparison tree)。

    查找方式为(找k):先与树根结点进行比较,若k小于根,则转向左子树继续比较,若k大于根,则转向右子树,递归进行上述过程,直到查找成功或查找失败。

    在n个元素的折半查找判定树中,由于关键字序列是用树构建的,所以查找路径实际为树中从根节点到被查结点的一条路径,因为比较次数刚好为该元素在树中的层数。所以:

    查找成功 的平均查找长度:
    在这里插入图片描述
    其中,Pi为查找k的概率,level(Ki)为k对应内部结点的层次。而在这样的判定树中,会有n+!种查找失败的情况,因为将判定树构建为完全二叉树,又有n+1个外部结点(用Ei(0<=i<=n)表示)

    查找失败 的平均查找长度:

    在这里插入图片描述

    qi表示查找属于Ei中关键字的概率,level(Ui)表示Ei对应外部结点的层次。

    在一颗有n个结点判定树中,

    在这里插入图片描述


    例子:计算二叉查找树的平均查找长度

    例:给11个数据元素有序表(2,3,10,15,20,25,28,29,30,35,40)采用折半查找。则ASL成功和不成功分别是多少?

    先画出判定树,
    在这里插入图片描述

    查找成功 的平均查找长度:
    在这里插入图片描述

    查找失败 的平均查找长度:
    在这里插入图片描述

    参考:https://www.cnblogs.com/ygsworld/p/10238729.html

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

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

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

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

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

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

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

    展开全文
  • ASL 指的是平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子: 0.7 处理冲突: 线性探测再散列法 查找成功的 ASL 计算方法: 因为现在的数据是 7 个,填充因子...

    开放地址查找成功的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
    成功 1 2 1 1 1 3 3
    不成功 3 2 1 2 1 5 4

    所以查找成功的计算:
    如果查找 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 计算方法

    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,依然不等。这个时候到了 地址为 2,发现为空,依然没有找到。所以停止查找,本次查找不成功。因为如果 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

    原博客地址:https://www.cnblogs.com/qixinbo/p/7782314.html


    链地址法

    假设散列表的长度是 13,散列函数为 H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。
    拉链法
    查找成功时的平均查找长度:

    ASL = (1*6+2*4+3*1+4*1)/12 = 7/4

    查找不成功时的平均查找长度:

    ASL = (4+2+2+1+2+1)/13

    注意:查找成功时,分母为哈希表元素个数,查找不成功时,分母为 mod 的 K 值。

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

    千次阅读 2019-07-11 10:13:24
    ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子(用来计算表长的): 0.7 处理冲突: 线性探测再散列法 查找成功的ASL计算方法: 因为现在的数据是...
  • 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{ ...
  • 有序线性表查找平均长度 ...长度为10的表,采用顺序查找法,平均查找长度ASL是? 如果一定可以找到的: 则10个数,每个被找到的概率是1/10; 每个元素被找到的长度分别是:1,2,3,。。,10; ASL=(1+2+3+。。+10...
  • 平均查找长度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 ...
  • 【hash表】hash表平均查找长度ASL

    千次阅读 2019-08-28 14:00:41
      hash 表在处理 collision 的时候有...  本文记录使用开链法的情况下,Hash 表查找成功和查找不成功的平均查找长度ASL - ),其他方法同理。   首先开链法是指,每一个表格元素维护一个list,hash function...
  • ASL = 1/n * (每个查找元素深度之和) OK,举个例子: 深度为1的25的一个元素; 深度为2的10和30的两个个元素; 深度为3的2、15、28、35的四个元素; 深度为4的3、20、29、40的四个元素; ...
  • (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度ASL1;当把含有n个节点的判定树看成是一棵满二叉树时,其成功情况下平均查找长度的人理论值ASL2...
  • 平均查找长度

    2018-12-14 09:32:00
    Hash表的平均查找长度ASL计算方法 Hash表的“查找成功的ASL”和“查找不成功的ASL” ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数:H(Key) = (key x 3) MOD 7 装载因子:...
  • 关于ASL(平均查找长度)的简单总结

    千次阅读 多人点赞 2019-01-08 15:42:00
    ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数成为平均查找长度。 它的定义是这样的: 其中n为查找表中元素个数,Pi...
  • 成功的ASL很简单,就是首先确定你要找的那个值,然后用hash进行查找计算,如果直接找到就是1次,如果hash(不一定就是原来的hash)的计算不止一次,就按你找到总共的次数计入。然后再套用公式计算就可以了,公式如下...
  • 数据结构几种平均查找长度

    千次阅读 2020-04-16 17:39:35
    总结的有关数据结构中平均查找长度ASL的三种计算小技巧: 1.顺序查找法的平均查找长度为:(n+1)/2 2.散列表的查找成功和查找不成功的平均查找长度 技巧(线性探测法和链地址法): ① 查找成功时的比较次数是...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 1 2 1 3 6 2 5 1 ...
  • 求折半查找成功时的平均查找长度

    千次阅读 2019-02-14 09:30:30
    /** * 实验题目: * 求折半查找成功时的平均查找长度 * 实验目的: * 深入掌握折半查找过程和折半查找算法分析 * 实验内容: ...* 1、输出n=11时的判定树并求成功情况下的平均查找长度ASL。 * 2、通过构...
  • 常见的平均查找长度总结

    万次阅读 多人点赞 2019-10-01 15:29:37
    1. 平均查找长度ASL) pi 是查找到某个元素的概率(probability) ci 是查找到这个元素时已经比较的次数,如,查找在 10 个数中查找第 5 个数,其比较的次数是多少(包括和第 5 个数比较的次数) 2. 顺序查找的...
  • 设关键字个数为n,在各关键字等概率查找的前提下, 1、顺序查找的平均查找长度ASL=(n+1)/2, 2、在n趋于无穷大时,折半查找的ASL=((n+1)log2(n+1))/n - 1,当n大于50时,ASL约等于log2(n+1)-1 3、设分块查找中将长为 n 的...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 344
精华内容 137
关键字:

平均查找长度asl