所以这是我的一个算法类的作业问题。我很难掌握整个复杂性/运行时间的东西，所以任何答案和解释将不胜感激！搜索大小为n的列表的平均比较次数？
考虑随机生成的大小为n的列表。 （a）如果列表以随机顺序存储，如果这些搜索的αn成功，我们将对M个搜索序列进行比较的预期（平均）数量是多少，即我们正在搜索一个项目在名单上。
（b）如果项目按顺序存储，那么预期的平均搜索次数是多少（因此 我们可以使用更有效的搜索策略，例如二分搜索）。
我感觉好像第一个问题的答案是n/2或者其他东西，但不知道如何计算α部分。
如果数字随机放置在列表中，并且所有M次搜索都会导致您找到该项目，那么预期的比较次数将为每次搜索n/2次。
想想这样。你正在寻找的物品有50％的机会位于列表的前半部分，50％的机会位于列表的后半部分。如果它位于列表的后半部分，则该子列表的前半部分有50％的机会，50％的后半部分有50％的机会。如果该项目位于列表的前半部分，则是同样的事情。
如果您执行n次唯一搜索（列表中的每个项目都有一次搜索），则比较的总次数为1 + 2 + 3 + 4 ... + n。这可以用于n*(n+1)/2比较。除以n，得到(n+1)/2。
如果你做M随机搜索，然后平均你会得到非常相似的结果。采用少于n/2次比较的搜索次数将近似平衡比n/2次比较多的次数。
现在，如果某些搜索不成功，它们会进行n次比较。所以平均值变得更像：
(successful*n/2 + unsuccessful*n)/M
好吧，我想不出如何考虑成功和失败的概念，但现在看到你的数学是完全合理的，谢谢 – Carly
我确信这是问题制定者期望的答案，但你怎么能假设正在搜索的项目的位置同样可能位于数组中的任何索引处？最好的问题是措辞不佳，并且缺少一些假设（例如，所有数组项都是唯一的，并且“随机顺序”意味着每个排列都是相同可能的，并且在排列数组之前选择搜索）。 –
@PaulHankin：是的，这个问题措辞不足，缺乏细节。基于过去遇到的类似问题，我对数据的性质做了一些假设。 –
永远不要写任何问题，说它是作业。这里的人会假定你在不求助的情况下寻求帮助。顺便说一句，我没有看到你的任何方法。 – surajsn