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