顺序查找的平均时间是多少？

[单选题]

顺序查找的平均时间是多少？

```
n/2
```
```
n
```
```
n * n
```
```
log n
```

武培轩

正确答案

答案解析

平均时间的计算方式如下
首先，假定这个数组的长度为n。
目标等概率出现在任意位置，即出现在每个位置的概率均为1/(n+1)，其中，找不到的概率也是1/(n+1)
然后，对于第i个位置，需要i次比较才能找出来，则找到的情况下，共需1+2+...+n次查询，即(n*(n+1))/2。
找不到的情况下，也是n次查询。
故平均时间为总比较数，除以位置数，即((n*(n+1))/2+n)/(n+1)=n/2+n/(n+1)。
如果一开始直接当找到，算出来就是(n+1)/2
两个结果都可以当作是n/2

发表于 2018-09-13 17:00:13 回复(0)

更多回答

推荐

牛客-007

答案：A

顺序查找，目标数据可能在序列的任意位置，平均位置是n/2

所以顺序查找平均时间是n/2

注意本题问的是平均时间，不是时间复杂度，时间复杂度只取数量级，略去常数为O(n)

编辑于 2015-02-02 18:12:53 回复(7)

魅之影_正

正确答案：A

平均时间的计算方式如下~
首先，假定这个数组的长度为n。
目标等概率出现在任意位置，即出现在每个位置的概率均为1/(n+1)，其中，找不到的概率也是1/(n+1)
然后，对于第i个位置，需要i次比较才能找出来，则找到的情况下，共需1+2+...+n次查询，即(n*(n+1))/2。
找不到的情况下，也是n次查询。
故平均时间为总比较数，除以位置数，即((n*(n+1))/2+n)/(n+1)=n/2+n/(n+1)。
如果一开始直接当找到，算出来就是(n+1)/2
两个结果都可以当作是n/2

发表于 2015-01-08 00:41:19 回复(1)