0 
RANDOM MIN(A[1::n])

min = infinity

for i = 1 to n in random order

        if A[i] < min
            min = A[i] ---- (*)
return min

第 k 次迭代执行 * 行的概率是多少？

我发现它是 1/n，除了第一次迭代。

原因是随机顺序生成n！可能的结果，在第 k 次迭代中，A[第 k 个生成的结果] 可以是 n 中的任何一个。并且为了使其最小，有 n 种可能性，因此是 1/n。

一个例子：对于 n = 3，k=2
输入：(10, 11, 12) 或 3 个的任意组合

permutations    if A[2] < min
  123              N
  132              N
  213              Y
  231              N 
  312              Y//edited mislabeled it earlier
  321              Y

行执行的第二次迭代中的概率与所有其他 1/n 相同，除了第一行是 1 因为它总是成立

如果我错了，请告诉我，因为我的教授说是 1/k，我对他的解释不满意！

4

2 回答 2

2

您混淆了“最小值在哪里”和“行是否被执行”的问题。

最小值位于一个均匀随机的位置，因此它以 1/N 的概率位于一个特定位置。

但是要找到它，您需要执行该行，并且这种情况发生的概率越来越小：

  1. A[1] 小于无穷大，概率为 1

  2. A[2] 小于 A[1] 的概率为 1/2。

等等。

于 2013-09-10T11:10:48.867 回答
1 
Round 1: 1 in 1 chance it is the smallest so far
Round 2: 1 in 2 chance it is the smallest so far
Round 3: 1 in 3 chance it is the smallest so far
Round 4: 1 in 4 chance it is the smallest so far
...
...
Round k: 1 in K chance it is the smallest so far
于 2013-09-10T11:11:25.470 回答