如何确定随机骰子卷产生的问题的最佳,更差和平均的案例复杂性？

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.验证这是维基页面(左栏)上的"概率质量函数".
• 几何分布的平均值是1/p,因此是100.这是找到特定图片所需的平均卷数.

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