1

我有NxN布尔矩阵，其中所有元素都有初始状态false

bool[][] matrix = GetMatrix(N);

在循环的每一步中，我想row i, column j在所有单元格中随机均匀地选择一个单元格 ( ) false，并将其设置为true直到某些条件发生。

使用哪种方法？我有这两种方式。

  • 从 中创建一个NxN数组0...(NxN-1)，使用均匀洗牌算法进行洗牌，而不是从该数组中依次取出第 i 个元素并设置矩阵 [i/N][i%N]。

使用O(N^2)额外的内存，初始化需要O(N^2)时间

第二个

  • 生成随机i，0...(N^2-1)如果 (i/N, i%N) 在矩阵中设置，重复随机生成直到创建未设置的元素。

这种方式不使用任何额外的内存，但我很难估计性能......这可能是一种情况，当设置除一个之外的所有元素并且随机重复很多次寻找空闲单元格时？我是对的，只要随机理论上均匀工作，这种情况就不应该经常发生吗？

4

2 回答 2

1

从 0...(N^2-1) 生成随机 i 并且如果 (i/N, i%N) 在矩阵中设置，则重复随机生成直到创建未设置的元素。

该算法的分析与优惠券收集问题相同。运行时间为 Theta(n^2 log n)。

于 2013-08-31T20:28:26.503 回答
1

我将尝试回答您的问题，并使用最坏的情况分析，正如您所指出的那样，除了一个以外的所有单元格都被占用。

让我们首先注意p = P(X = m) = 1/N^2. 由此，我们得出 k在获得所需结果之前您必须等待投掷的概率是P( Y = k) = p * (1-p)^(k-1)。这意味着，因为N = 10您需要 67 个随机数才能获得大于 50% 的概率，而 457 个随机数具有大于 99% 的概率。

k给出获得概率大于获得价值所需的投掷次数的一般公式alpha是：

k > (log(1 - alpha) / log(1-p)) -1

其中p定义如上，等于1/N^2

随着 N 变大，情况可能会变得更糟。您可以考虑创建一个您需要的索引列表并随机获取一个。

于 2013-08-31T20:30:29.483 回答