当表长为n的顺序表进行查找时,在查找概率相等的情况下,查找成功的平均查找长度为 (n+1)/2 ,为什么
时间: 2023-03-19 17:22:01 浏览: 212
这是因为在顺序表中,数据元素是按照顺序依次存储的,而查找的过程就是从表头开始逐一比较,直到找到目标元素或者遍历整个表。
当查找概率相等时,每个元素被查找的概率都是1/n。因此,平均查找长度就是每个元素查找时需要遍历的次数之和再除以元素个数,即:
(n-1)/2 + (n-2)/2 + ... + 1/2 + 0/2 / n
化简后可以得到:
(n-1+1)/2 = (n-1)/2
所以,当表长为n的顺序表进行查找时,在查找概率相等的情况下,查找成功的平均查找长度为 (n-1)/2。
相关问题
)长度为 12 的有序表采用顺序存储结构,采用折半查找技术,在等概率情况下,查找成功时的平均查找长度是多少
在等概率情况下,折半查找成功的概率为 1/12,失败的概率为 11/12。当查找成功时,需要查找的次数为 1,因此平均查找长度为 1*(1/12) = 1/12。当查找失败时,每次可以排除表中一半的元素,因此需要查找的次数为 log2(12) ≈ 3.58,因此平均查找长度为 3.58*(11/12) ≈ 3.30。因此,折半查找成功时的平均查找长度约为 1/12,失败时的平均查找长度约为 3.30。
对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为
在对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度ASL(Average Search Length)为:
```
ASL = (1/N) * (1 + 2 + 3 + ... + N)
```
即
```
ASL = (1/N) * N(N+1)/2
```
化简得
```
ASL = (N+1)/2
```
因此,平均查找长度为 `(N+1)/2`。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)