顺序比较还是随机比较更有效？

Question

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

这里有一些伪代码可以帮助解释我的想法：

顺序：

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 它可能会在第一次尝试时得到它，但理论上它可能永远不会得到它。

Answer 1

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

对于您的随机搜索，比较的次数是 geometric random variable（一个变量，它给出了一系列独立伯努利试验中第一次成功的试验），参数为 p = 1/5。这种变量的预期值为 1/p，在本例中为 5.

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

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

顺序比较还是随机比较更有效？

Is sequential or random comparison more efficient?

performance

random

coding-efficiency

sequential-number

顺序：

随机：