1

我想知道（纯粹出于好奇）按顺序或随机比较数字是否更有效。我最初认为按顺序比较数字会更有效，但我不确定，我知道如何解决这个问题，所以我想我会问社区。

这是一些伪代码来帮助解释我的想法：

顺序：

x = 1
y = random (1 to 5)

if (x == y){
  //finished
} else {
  x++
}

这只会x每次加一，直到它达到与 相同的值y。例如，如果x是5它需要五轮才能完成，但是如果x是1它会在第一次尝试时完成。

随机的：

x = random (1 to 5)
y = random (1 to 5)

if (x == y){
  //finished
} else {
  x = New random (1 to 5)
}

每次都会设置x一个新的数字。例如，如果x曾经5和y曾经是5它可能会在第一次尝试时得到它，但理论上它可能永远不会得到它。

4

1 回答 1

2

对于您的顺序搜索，预期的比较次数与 的预期值相同y，即 3。

对于您的随机搜索，比较次数是一个几何随机变量（在一系列独立伯努利试验中给出第一次成功试验的变量），参数为p = 1/5。这种变量的期望值1/p在这种情况下是 5。

由于 5 > 3，平均而言，第二种方法比第一种方法涉及更多的比较。在实践中，第二种方法的平均运行时间将比这个论点所暗示的要差得多，因为循环遍历连续整数很快，但随机数生成相对较慢。

对于任意n而不是n = 5，将(n+1)/2在第一种情况和n第二种情况下进行比较的平均值。因此，随机搜索平均需要两倍的步数。此外，在第一种情况和第二种情况下，所需比较次数的方差是(n^2-1)/12（通过thisn^2-1 ） ，因此在随机搜索的情况下存在更多的可变性。如果您是一个乐观主义者，这意味着您有更高的机会进行比预期数量显着减少n的比较。但有时需要更多的东西来平衡这一点。例如，使用n=5时，随机搜索将使用超过 10 次比较的概率为 (4/5)^10 = 10.7%。

于 2017-05-07T13:58:10.417 回答