ASL
哈希表
链地址
查找成功时的平均查找长度
ASL成功 = 表中每个元素查找成功时的比较的次数 / 待查找的所有元素的个数
ASL成功 = (1 * 5 + 2 * 2 + 3 * 1) / 8
查找失败时的平均查找长度
ASL失败 = 每个链表上一直查找到空所需要的次数 / 表的长度
ASL失败 = (4 + 1 + 1+ 3 + 1 + 1 + 2 + 2 + 1 + 2) / 10
散列表
查找成功时的平均查找长度
ASL成功 = 从计算得到的位置往后查查到现在位置需要的次数 / 待查找所有元素的个数
ASL成功 = (1 + 2 + 1 + 1 + 1 + 3 + 3) / 7
查找失败时的平均查找长度
ASL失败 = 表中从0~MOD-1中每个格子到下一个空格子需要的查找次数 / MOD的数(因为结果只有可能在0~MOD里面)
ASL失败 = (3 + 2 + 1 + 2 + 1 + 5 + 4 ) / 7
顺序查找
查找方式为从头查到尾,找到待查找元素则为成功,找到尾部仍未找到则为失败,所以Ci(第i个元素的比较次数)取决于它在表中的位置
ASL成功 = \(\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}\)
ASL失败 = \(n\)
折半查找
化为二叉排序树(判定树)
二叉排序树
ASL成功 = \(\sum\limits_{i=1}^{n}P_i * level(k_i)\)(Pi为查找k的概率,level(Ki)为k对应内部结点的层次)
ASL失败 = \(\sum\limits_{i=0}^{n}q_i* level(U_i)\)(有n + 1个外部结点,用Ei(0 <= i <= n)表示,qi表示查找属于Ei中关键字的概率,level(Ui)表示Ei对应外部结点的层次)
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 眨眼的小星星!