【性能分析】 分析査找算法的效率,通常用平均査找长度ASL来衡量。 定义:在查找成功时,平均查找长度ASL是指为确定数 据元素在表中的位置所进行的关键码比较次数潲期望俚;C 对一个含n个数据元素的表,查找成功时 P=1 其中:P为表中第i个数据元素的查找概率, C:为表中第i个数据元素的关键码与给定值kx相等时 按算法定位时关键码的比较次数。显然,不同的查找方法, C:可以不同。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 【性能分析】 分析查找算法的效率，通常用平均查找长度ASL来衡量。 定义：在查找成功时，平均查找长度ASL是指为确定数 据元素在表中的位置所进行的关键码比较次数的期望值。 对一个含n个数据元素的表，查找成功时 其中：Pi为表中第i个数据元素的查找概率， Ci为表中第i个数据元素的关键码与给定值kx相等时， 按算法定位时关键码的比较次数。显然，不同的查找方法， Ci可以不同。 ASL= Pi·Ci n ∑i=1 n ∑i=1 Pi=1
C1为表中第个数据元素的关键码与给定值kx相等时,按算 法定位时关键码的比较次数。显然,不同的查找方法,C:可 以不同 就上述算法而言,对于n个数据元素的表,给定值kx与表 中第i个元素关键码相等,即定位第i个记录时,需进行n i+1次关键码比较,即C;=n-i+1。则査找成功时,顺序查找 的平均查找长度为 ASL=、P;(n-i+1) 设每个数据元素的查找概率相等,则等概率情况下有 ASL=31(m+1)=n+1 n 查找不成功时,关键码的比较次数总是n+1次 算法中的基本工作就是关键码的比较,因此,查找长 度的量级就是查找算法的时间复杂度,其为0(n)。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 Ci为表中第i个数据元素的关键码与给定值kx相等时，按算 法定位时关键码的比较次数。显然，不同的查找方法，Ci可 以不同。 就上述算法而言，对于n个数据元素的表，给定值kx与表 中第i个元素关键码相等，即定位第i个记录时，需进行ni+1次关键码比较，即Ci =n-i+1。则查找成功时，顺序查找 的平均查找长度为: 设每个数据元素的查找概率相等，则等概率情况下有 查找不成功时，关键码的比较次数总是 n+1 次。 算法中的基本工作就是关键码的比较，因此，查找长 度的量级就是查找算法的时间复杂度，其为O(n)。 ASL= n Pi·（n-i+1） ∑i=1 n ∑i=1 ASL= １─ （n-i+1）= ｎ ｎ＋１ ─── ２
许多情况下,查找表中数据元素的查找 概率是不相等的。为了提高查找效率,查找 表需依据査找概率越高,比较次数越少;査 找概率越低,比较次数就较多的原则来存储 数据元素。 顺序查找缺点是当n很大时,平均查找 长度较大,效率低;优点是对表中数据元素 的存储没有要求。另外,对于线性链表,只 能进行顺序查找。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 18 许多情况下，查找表中数据元素的查找 概率是不相等的。为了提高查找效率，查找 表需依据查找概率越高，比较次数越少；查 找概率越低，比较次数就较多的原则来存储 数据元素。 顺序查找缺点是当n很大时，平均查找 长度较大，效率低；优点是对表中数据元素 的存储没有要求。另外，对于线性链表，只 能进行顺序查找
923有序表的折半查找 有序表即是表中数据元素按关键码升序或降序排列。 折半查找的思想为:在有序表中,取中间元素作为 比较对象,若给定值与中间元素的关键码相等,则查找 成功;若给定值小于中间元素的关键码,则在中间元素 的左半区继续查找;若给定值大于中间元素的关键码 则在中间元素的右半区继续查找。不断重复上述查找过 程,直到査找成功,或所查找的区域无数据元素,查找 失败。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 19 有序表即是表中数据元素按关键码升序或降序排列。 折半查找的思想为：在有序表中，取中间元素作为 比较对象，若给定值与中间元素的关键码相等，则查找 成功；若给定值小于中间元素的关键码，则在中间元素 的左半区继续查找；若给定值大于中间元素的关键码， 则在中间元素的右半区继续查找。不断重复上述查找过 程，直到查找成功，或所查找的区域无数据元素，查找 失败。 9.2.3 有序表的折半查找
【步骤】 ①1ow=l;high= Length;∥设置初始区间 ②当 low high时,返回查找失败信息/表空,查找 失败 3 lowshigh, mid=(lowthigh)/2 ∥取中点 a.若kx<tbl. elem[mid].key,high=mid-1;转② ∥查找在左半区进行 b.若 kxtbl elem[mid]. key,low=mid+1;转② ∥查找在右半区进行 C.若kx= tbl. elemmio]key,返回数据元素在表中位 置 ∥查找成功 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 20 【步骤】 ① low=1；high=length； // 设置初始区间 ② 当low>high时，返回查找失败信息 //表空，查找 失败 ③ low≤high，mid=(low+high)/2; //取中点 a. 若kx<tbl.elem[mid].key，high=mid-1；转② // 查找在左半区进行 b. 若kx>tbl.elem[mid].key，low=mid+1；转② // 查找在右半区进行 c. 若kx=tbl.elem[mid].key，返回数据元素在表中位 置 // 查找成功