如题所述
首先,这里的顺序查找算法应该是包含哨兵的算法(就是令数组下标为0的元素的值为你要查找的关键字)。查找失败意味着n个元素都比较过了,接下来会比较下一个元素,即最后的哨兵元素(注意是从后往前查找的),然后跳出查找的循环语句。所以一共比较了n+1次。
平均查找长度公式是概率乘比较次数的求和。假设每个元素查找概率为1/n,而失败时每个元素都相当于比较n+1次,即查找失败时每个元素的查找长度一样,都是(n+1)/n。不算哨兵元素,一共有n个元素进行了查找,故ASL=n*(n+1/n)=n+1
平均查找长度公式是概率乘比较次数的求和。假设每个元素查找概率为1/n,而失败时每个元素都相当于比较n+1次,即查找失败时每个元素的查找长度一样,都是(n+1)/n。不算哨兵元素,一共有n个元素进行了查找,故ASL=n*(n+1/n)=n+1
温馨提示:答案为网友推荐,仅供参考