algorithm - 您如何确定随机掷骰子产生的问题的最佳、最差和平均情况复杂度？

Question

有一本100页的绘本。如果随机掷骰子以选择其中一页，然后重新掷骰子以搜索书中的某个图片——我如何确定这个问题的最佳、最差和平均情况复杂度？

建议的答案：

最佳情况：在第一个骰子上找到图片

最坏的情况：在第 100 个骰子上找到图片或图片不存在

平均情况：在 50 次掷骰子后找到图片 (= 100 / 2)

假设：不正确的图片最多搜索一次

Answer 1

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

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，因此请使用 Wikipedia 页面上表格的左侧列。）

Answer 2

为了分析这一点，想想最好的、最坏的和平均的情况是什么。您需要回答三个问题才能找到这三种情况：

1. 找到所需页面的最少滚动数是多少？
2. 找到所需页面的最大滚动数是多少？
3. 找到所需页面的平均滚动数是多少？

一旦你找到了前两个，第三个应该就不那么棘手了。如果您需要渐近符号而不仅仅是卷数，请考虑如果您更改书中的页数（例如 200 页 vs 100 页 vs 50 页），每个问题的答案会如何变化。

Answer 3

最坏的情况不是在 100 次掷骰子后找到的页面。那就是你的骰子总是返回不同的数字。最坏的情况是你永远找不到页面（你陈述问题的方式）。

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

平均情况是：

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

是的，总和是无限的，因为在考虑最坏的情况时，我们确定您可能有任意数量的骰子掷骰。这并不意味着它不能被计算（它可能意味着，但它不是必须）。

第一次尝试找到该页面的概率为1/100。在第二次掷骰子时找到它的概率是多少？

Answer 4

你快到了，但 (1 + 2 + ... + 100)/100 不是 50。

观察你的随机选择方法可能会有助于观察你的随机选择方法相当于随机洗牌整个牌组，然后按顺序搜索你的目标。每个位置的可能性相同，因此平均值很容易计算。当然，除了你没有预先做所有这些工作，就像生成每个随机数和访问相应元素所需的一样多。

请注意，如果您的图书存储为链接列表，那么从每个随机选择的页面移动到下一个选择的成本取决于它们之间的距离，这将使分析变得相当复杂。您实际上并没有声明您具有恒定时间的访问权限，并且“真正的书”是否提供了这一点可能存在争议。

就此而言，有不止一种方法可以选择不重复的随机数，而且并非所有的随机数都具有相同的运行时间。

因此，您需要更多详细信息才能根据“访问的页面数”以外的任何内容分析算法。