如何确定随机掷骰子生成的问题的最佳、最差和平均情况复杂度?

发布于 2024-08-19 02:54:50 字数 226 浏览 10 评论 0原文

有一本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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

小镇女孩 2024-08-26 02:54:50

鉴于您对问题的描述,我认为您的假设(不正确的图片仅“搜索”一次)听起来不正确。如果你不做这个假设,那么答案如下所示。您会发现答案与您提出的有些不同。

  1. 您有可能第一次尝试就成功。因此,第一个答案是 1。
  2. 如果你运气不好,你可能会永远滚动错误的数字。所以第二个答案是无穷大。
  3. 第三个问题不太明显。

平均卷数是多少?您需要熟悉几何分布:获得一次成功所需的试验次数。

  • 定义p为试验成功的概率; p=0.01。
  • 设 Pr(x = k) 为第 k 次成功尝试的概率。那么我们将必须有 (k-1) 次失败和一次成功。所以 Pr(x=k) = (1-p)^(k-1) * p。验证这是否是 wiki 页面(左栏)上的“概率质量函数”。
  • 几何分布的平均值为 1/p,因此为 100。这是找到特定图片所需的平均滚动数。

(注意:我们需要将 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.

  1. It is possible that you could be successful on the first attempt. Therefore, the first answer is 1.
  2. If you were unlucky, you could keep rolling the wrong number forever. So the second answer is infinity.
  3. The third question is less obvious.

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.

  • Define p as the probability for a successful trial; p=0.01.
  • Let Pr(x = k) be the probability that the first successful trial being the k th. Then we're going to have to have (k-1) failures and one success. So Pr(x=k) = (1-p)^(k-1) * p. Verify that this is the "probability mass function" on the wiki page (left column).
  • The mean of the geometric distribution is 1/p, which is therefore 100. This is the average number of rolls required to find the specific picture.

(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.)

若有似无的小暗淡 2024-08-26 02:54:50

要对此进行分析,请考虑实际上最好、最差和平均情况是什么。您需要回答三个问题才能找到这三种情况:

  1. 找到所需页面所需的最少卷数是多少?
  2. 找到所需页面的最大卷数是多少?
  3. 找到所需页面的平均卷数是多少?

一旦找到前两个,第三个就不会那么棘手了。如果您需要渐近符号而不仅仅是卷数,请考虑如果您更改书中的页数(例如 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:

  1. What is the fewest number of rolls to find the desired page?
  2. What is the largest number of rolls to find the desired page?
  3. What is the average number of rolls to find the desired page?

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).

一世旳自豪 2024-08-26 02:54:50

最坏的情况不是 100 次掷骰子后找到的页面。那就是你的骰子总是返回不同的数字。最糟糕的情况是您永远找不到该页面(按照您陈述问题的方式)。

幸运的是,平均情况并不是最好和最坏情况的平均。

平均情况是:

  1 * (probability of finding page on the first dice roll)
+ 2 * (probability of finding page on the second dice roll)
+ ...

是的,总和是无限的,因为在考虑最坏的情况时,我们确定您可能有任意大量的骰子掷出。这并不意味着它不能被计算(它可能意味着,但不一定如此)。

第一次尝试找到该页面的概率是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:

  1 * (probability of finding page on the first dice roll)
+ 2 * (probability of finding page on the second dice roll)
+ ...

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?

昇り龍 2024-08-26 02:54:50

你已经快到了,但是 (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".

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文