Question

一道关于计算机的题！求解

在长度为N的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。那么在平均情况下需要比较的次数大约为？
答案是四分之三N 为什么啊 我是计算机小白 TAT可以给个详细的解答吗 谢谢了！

Answer 1

如果该元素在顺序表中，因为每个位置上的可能性一样，所以平均而言我们需要查找二分之一N个元素。如果不在顺序表中，则我们需要查找N个元素（因为我们需要每个都检查一遍）。所以 二分之N加N的平均值为答案，即四分之三N。