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

Question

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

建议的答案:

最好的情况:在第一个骰子上找到图片

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

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

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

Answer 1

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

1. 您有可能在第一次尝试时就成功。因此，第一个答案是 1。
2. 如果你运气不好，你可能会一直掷错数字。所以第二个答案是无穷大。
3. 第三个问题不太明显。

平均卷数是多少？您需要熟悉 Geometric Distribution :获得一次成功所需的试验次数。

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

(注意:我们需要将 1 视为可能的最低值，而不是 0，因此请使用维基百科页面上表格的左侧列。)