如何确定随机掷骰子生成的问题的最佳、最差和平均情况复杂度？
有一本100页的图画书。如果随机掷骰子来选择其中一页，然后重新掷骰子以搜索书中的特定图片 - 我如何确定这个问题的最佳、最差和平均情况复杂度？
建议答案：
最佳情况：在第一次掷骰子时找到图片
最差情况：在第 100 次掷骰子时找到图片或图片不存在
平均情况：在 50 次掷骰子后找到图片 (= 100 / 2)
假设：最多搜索一次错误图片
There is a picture book with 100 pages. If dice are rolled randomly to select one of the pages and subsequently rerolled in order to search for a certain picture in the book -- how do I determine the best, worst and average case complexity of this problem?
Proposed answer:
best case: picture is found on the first dice roll
worst case: picture is found on 100th dice roll or picture does not exist
average case: picture is found after 50 dice rolls (= 100 / 2)
Assumption: incorrect pictures are searched at most one time
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
鉴于您对问题的描述，我认为您的假设（不正确的图片仅“搜索”一次）听起来不正确。如果你不做这个假设，那么答案如下所示。您会发现答案与您提出的有些不同。
平均卷数是多少？您需要熟悉几何分布：获得一次成功所需的试验次数。
（注意：我们需要将 1 视为可能的最低值，而不是 0，因此请使用维基百科页面上表格的左侧列。）
Given your description of the problem, I don't think your assumption (that incorrect pictures are only "searched" once) sounds right. If you don't make that assumption, then the answer is as shown below. You'll see the answers are somewhat different from what you proposed.
What is the average number of rolls? You need to be familiar with the Geometric Distribution: the number of trials needed to get a single success.
(Note: We need to consider 1 as the lowest possible value, rather than 0, so use the left hand column of the table on the Wikipedia page.)
要对此进行分析，请考虑实际上最好、最差和平均情况是什么。您需要回答三个问题才能找到这三种情况：
一旦找到前两个，第三个就不会那么棘手了。如果您需要渐近符号而不仅仅是卷数，请考虑如果您更改书中的页数（例如 200 页与 100 页与 50 页），每个问题的答案将如何变化。
To analyze this, think about what the best, worst and average cases actually are. You need to answer three questions to find those three cases:
Once you find the first two, the third should be less tricky. If you need asymptotic notation as opposed to just the number of rolls, think about how the answers to each question change if you change the number of pages in the book (e.g. 200 pages vs 100 pages vs 50 pages).
最坏的情况不是 100 次掷骰子后找到的页面。那就是你的骰子总是返回不同的数字。最糟糕的情况是您永远找不到该页面（按照您陈述问题的方式）。
幸运的是，平均情况并不是最好和最坏情况的平均。
平均情况是：
是的，总和是无限的，因为在考虑最坏的情况时，我们确定您可能有任意大量的骰子掷出。这并不意味着它不能被计算（它可能意味着，但不一定如此）。
第一次尝试找到该页面的概率是
1/100。第二次掷骰子时找到它的概率是多少？The worst case is not the page found after 100 dice rolls. That would be is your dice always returned different numbers. The worst case is that you never find the page (the way you stated the problem).
The average case is not average of the best and worst cases, fortunately.
The average case is:
And yes, the sum is infinite, since in thinking about the worst case we determined that you may have an arbitrarily large number of dice rolls. It doesn't mean that it can't be computed (it could mean that, but it doesn't have to).
The probability of finding the page on the first try is
1/100. What's the probability of finding it on the second dice roll?你已经快到了，但是 (1 + 2 + ... + 100)/100 不是 50。
观察你的随机选择方法可能会有所帮助，这相当于随机洗整整副牌，然后搜索它以找到你的目标。每个位置的可能性均等，因此平均值很容易计算。当然，除了您不需要预先完成所有工作，只需生成每个随机数并访问相应元素所需的工作即可。
请注意，如果您的书存储为链接列表，那么从每个随机选择的页面移动到下一个选择的成本取决于它们之间的距离，这将使分析变得相当复杂。您实际上并没有声明您具有恒定时间的访问权限，并且“真正的书”是否提供了这一点可能是有争议的。
就此而言，有不止一种方法可以选择不重复的随机数，并且并非所有方法都具有相同的运行时间。
因此，您需要更多详细信息才能根据“访问的页面数”以外的任何内容来分析算法。
You're almost there, but (1 + 2 + ... + 100)/100 isn't 50.
It might help to observe that your random selection method is equivalent to randomly shuffling the whole deck and then searching it in order for your target. Each position is equally likely, so the average is straightforward to calculate. Except of course that you aren't doing all that work up front, just as much as is needed to generate each random number and access the corresponding element.
Note that if your book were stored as a linked list, then the cost of moving from each randomly-selected page to the next selection depends on how far apart they are, which will complicate the analysis quite a lot. You don't actually state that you have constant-time access, and it's possibly debatable whether a "real book" provides that or not.
For that matter, there's more than one way to choose random numbers without repeats, and not all of them have the same running time.
So, you'd need more detail in order to analyse the algorithm in terms of anything other than "number of pages visited".