search - 顺序搜索作业问题

Question

考虑一个包含 100 条记录的磁盘文件 a. 如果已知记录在文件中，则使用顺序搜索查找记录平均需要多少次比较？

我发现这是 100/2 = 50。

湾。如果记录有 68% 的概率出现在文件中，那么平均需要进行多少次比较？

这是我遇到麻烦的部分。起初我以为是 68% * 50，但后来想想就错了。然后我以为是(100% - 68%) * 50，但我还是觉得那是错误的。有什么提示吗？

Answer 1

我会像这样将其分解为加权平均值。

它有 68% 的机会在文件中；在这种情况下，您在第一部分的结果平均需要进行 50 次比较。

32% 的机会记录不在文件中；在这种情况下，您需要查看每条记录，即 100 次比较。

0.68*50 + 0.32*100 = 平均 66 次比较。

但是我已经有一段时间没有上过概率课程了……