顺序查找中 若成功与不成功的概率相等 对每个记录查找的概率为1/(2n)求它的平均查找长度
时间: 2024-04-16 08:25:07 浏览: 32
如果在顺序查找中,成功和不成功的概率相等,并且每个记录的查找概率为 1/(2n),我们可以计算平均查找长度。
假设有 n 个记录,每个记录的查找概率为 p = 1/(2n)。则查找成功的概率为 p,查找失败的概率也为 p。
对于成功查找的平均查找长度,需要进行 n/2 次比较操作(在平均情况下,每个记录需要比较一次)。因此,成功查找的平均查找长度为 n/2。
对于不成功查找的平均查找长度,需要进行 n 次比较操作(在平均情况下,需要遍历整个列表才能确定目标元素不存在)。因此,不成功查找的平均查找长度为 n。
平均查找长度 = (成功查找的平均查找长度 * 成功查找的概率) + (不成功查找的平均查找长度 * 不成功查找的概率)
= (n/2 * p) + (n * p)
= n/2p + np
= (n + 2n)/2p
= 3n/(2p)
= 3n/(2 * 1/(2n))
= 6
因此,当成功和不成功的概率相等且每个记录的查找概率为 1/(2n) 时,顺序查找的平均查找长度为 6。
相关问题
当表长为n的顺序表进行查找时,在查找概率相等的情况下,查找成功的平均查找长度为 (n+1)/2 ,为什么
这是因为在顺序表中,数据元素是按照顺序依次存储的,而查找的过程就是从表头开始逐一比较,直到找到目标元素或者遍历整个表。
当查找概率相等时,每个元素被查找的概率都是1/n。因此,平均查找长度就是每个元素查找时需要遍历的次数之和再除以元素个数,即:
(n-1)/2 + (n-2)/2 + ... + 1/2 + 0/2 / n
化简后可以得到:
(n-1+1)/2 = (n-1)/2
所以,当表长为n的顺序表进行查找时,在查找概率相等的情况下,查找成功的平均查找长度为 (n-1)/2。
在一个长度为n的线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x同元素的平均比较次数,查找每个元素的概率都相等)为( )。
在一个长度为n的线性表中,采用顺序查找的平均查找长度可以表示为:
```
ASL = (1/n)*((1+2+...+n-1+n)/2)
```
其中,n为元素个数,1/n为每个元素被查找到的概率,括号中的式子为查找成功时需要比较的次数。将式子中的等差数列求和,得到:
```
ASL = (n+1)/2
```
所以,当采用顺序查找时,查找成功时的平均查找长度为(n+1)/2。