哈希表

链地址

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

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对应外部结点的层次)