顺序搜索作业问题
考虑一个包含 100 条记录的磁盘文件 一个。如果已知记录位于文件中,那么使用顺序搜索平均需要进行多少次比较才能找到该记录?
我发现这是 100/2 = 50
。如果该记录有 68% 的概率出现在文件中,那么平均需要多少次比较?
这是我遇到麻烦的部分。一开始我以为是68%*50,后来想了想,发现不对。然后我认为是(100% - 68%) * 50,但我仍然觉得这是错误的。有什么提示吗?
Consider a disk file containing 100 records
a. How many comparisons would be required on the average to find a record using sequential search, if the record is known to be in the file?
I figured out that this is 100/2 = 50.
b. If the record has a 68% probability of being in the file, how many comparisons are required on average?
This is the part I'm having trouble with. At first I thought it was 68% * 50, but then realized that was wrong after thinking about it. Then I thought it was (100% - 68%) * 50, but I still feel that that is wrong. Any hints?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
我会像这样将其分解为加权平均值。
它有 68% 的机会出现在文件中;在这种情况下,第一部分中的结果平均需要进行 50 次比较。
记录不在文件中的可能性为 32%;在这种情况下,您将需要查看每条记录,即 100 次比较。
0.68*50 + 0.32*100 = 平均 66 次比较。
但自从我上概率课程以来已经有一段时间了......
I'd break it down like this, into a weighted average.
A 68% chance of it being in the file; under these circumstances an average of 50 comparisons will be needed from your result in part I.
A 32% chance of the record NOT being in the file; under these circumstances you will need to look through every record, i.e 100 comparisons.
0.68*50 + 0.32*100 = 66 comparisons on average.
But it has been a while since I took a course on probability...