顺序查找平均比较次数对长度为n的顺序表进行顺序查找,问平均比较次数是多少?答案给出的是:n/2.（这是某名校考过的原题,答案好多资料上也都是n/2.）如果按照严蔚敏书上的解释,平均查找

Question

顺序查找平均比较次数
对长度为n的顺序表进行顺序查找,问平均比较次数是多少?
答案给出的是:n/2.（这是某名校考过的原题,答案好多资料上也都是n/2.）
如果按照严蔚敏书上的解释,平均查找长度是 (n+1)*3/4
如果按照题目给出的答案推的话,我猜测是：
总的比较次数是（n+1）*(n+2)/2,而有n种查找成功的情况,再加上1种不成功的情况,共n+1种情况；
那么答案应该是(n+2)/2；也不是n/2啊,很是纠结.
你们认为应该是多少呢?请给出理由.
另外,如果能够清晰的解释一下平均比较次数和平均查找长度的区别就更好了!

Answer 1

你算出来的(n+2)/2,当n->无穷大的时候,就是n/2啦.其实算法复杂度,关注的是数量级,而不是细节.
(n+1)*3/4的那个值,她的假设前提是,查的到和查不到2种情况各占50%.
你的值,你的假设是,查不到的情况只占1/n.
n/2,则假设查到的情况占100%.
平均比较次数和平均查找长度应该只是字面上写法不同,其实意思没什么区别.