2）仅考虑查找不成功的情况若k值不在表中，则总是需要n次比较之后才能确定查找失败，所以仅仅考虑查找不成功时对应的平均查找长度为：ASL不成功=n16/64
2）仅考虑查找不成功的情况 若k值不在表中，则总是需要n次比较之后才能确定查找失败，所以 仅仅考虑查找不成功时对应的平均查找长度为： ASL不成功 = n 16/64
3）既考虑查找成功文考虑查找不成功的情况一个顺序表中顺序查找的全部情况（查找成功和失败）可以用一棵判定树或比较树（这里是单支二叉树）来描述。例如，n=5的关键字序列（18，16，14，12，20）的顺序查找过程对应的判定树如下：Pe18R[0].key+k16pR[1].key+k14P2R[2].key+k12PR[3].keyk20P4R[4].key*k17/64
3）既考虑查找成功又考虑查找不成功的情况 一个顺序表中顺序查找的全部情况（查找成功和失败）可以用一棵判 定树或比较树（这里是单支二叉树）来描述。 例如，n=5的关键字序列（18，16，14，12，20）的顺序查找过程对 应的判定树如下： R[4].key≠k R[1].key≠k R[2].key≠k R[3].key≠k R[0].key≠k q p0 p1 p2 p3 p4 18 20 16 14 12 17/64
设所有成功查找的概率，9表示不成功查找的概率，当既考虑查找成功又考虑查找不成功的情况时有p+q=1。不妨假设p=q=0.5，并且所有关键字成功查找的概率相同，即p;=0.5/n，则成功情况下的平均查找长度为：-10.5n+1eASL动 = Z pic -"×(i+1)=0.5×2i=0i=018/64
设所有成功查找的概率，q表示不成功查找的概率，当既考虑查找成功又 考虑查找不成功的情况时有p+q=1。 不妨假设p=q=0.5，并且所有关键字成功查找的概率相同，即pi=0.5/n， 则成功情况下的平均查找长度为： 18/64
假设所有不成功查找的情况为m种，它们的查找概率相同，即9=0.5/m，则不成功情况下的平均查找长度为：mm0.5ASL不成功×n)=0.5nqixnmi=1i=1合起来：3n+1ASL= ASL成功 + ASL不成功 = 0.5×"1,+0.5×n=442可以推出：顺序查找的时间复杂度为o(n）。19/64
假设所有不成功查找的情况为m种，它们的查找概率相同，即qi=0.5/m， 则不成功情况下的平均查找长度为： 合起来： 可以推出：顺序查找的时间复杂度为O(n)。 19/64
顺序查找总结顺序查找的优点是算法简单，且对查找表的存储结构无特殊要求，无论是用顺序表还是用链表来存放元素，也无论是元素之间是否按关键字有序，它都同样适用。顺序查找的缺点是查找效率低，因此，当n较大时不宜采用顺序查找。20/64
顺序查找的优点是算法简单，且对查找表的存储结构无特殊要求，无论 是用顺序表还是用链表来存放元素，也无论是元素之间是否按关键字有 序，它都同样适用。 顺序查找的缺点是查找效率低，因此，当n较大时不宜采用顺序查找。 顺序查找总结 20/64