纯数学： 让我们计算rand()两种情况下函数调用的数量并比较结果：
让我们看看i = k已经选择了k个数字时对step调用的数学期望。通过一次rand()呼叫获得号码的概率等于p = (n-k)/n。我们需要知道这样的通话数量的数学期望，这会导致获得我们还没有的号码。
使用1call 获得它的概率为p。使用2电话- q * p，其中q = 1 - p。在一般情况下，在n致电后准确获得的可能性为(q^(n-1))*p。因此，数学期望为Sum[ n * q^(n-1) * p ], n = 1 --> INF。该总和等于1/p（由Wolfram alpha证明）。
因此，在该步骤上，i = k您将执行1/p = n/(n-k)该rand()函数的调用。
现在让我们对其进行整体总结：
Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T-数量rand方法1中调用 这里T = Sum[ 1/(n - k) ], k = 0 --> m - 1
在大多数实现中，这rand()称为内部random_shuffle n - 1时间。
现在，要选择方法，我们必须比较这两个值：n * T ? n - 1。 因此，要选择适当的方法，请T按照上述方法进行计算。如果T < (n - 1)/n最好使用第一种方法。否则，请使用第二种方法。
602392714
清零编程群