平均查找长度 平均查找长度( ASL-Average Search Length) 在查找过程中,对每个结点记录中的关键字要进行反复 比较,以确定其位置。因此,与关键字进行比较的平 均次数,就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ●对含有n个数据元素的查找表,查找成功时的平均查找 长度为: ASL=∑Pi米Ci 上一页 其中: 停止放映 Ci为查找第i个数据元素时需比较的次数=1 Pi为查找表中第i个数据元素的概率,且∑ 页 显然,C随查找过程及DS的不同而各异。 第7页下一页 上一页 停止放映 第 7 页 平均查找长度 ⚫ 平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复 比较，以确定其位置。因此，与关键字进行比较的平 均次数，就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ⚫ 对含有n个数据元素的查找表，查找成功时的平均查找 长度为： ASL =  Pi * Ci 其中： Pi 为查找表中第i个数据元素的概率，且  Pi = 1 Ci为查找第i个数据元素时需比较的次数。 显然，Ci随查找过程及DS的不同而各异。 i=1 n i=1 n