随机数组插入的时间复杂度

Question

所以我不得不随机插入N个元素到一个大小为N的数组中，但是我不确定程序的时间复杂度

程序基本上是：

for (i = 0 -> n-1){
    index = random (0, n); (n is exclusive)
    while (array[index] != null)
         index = random (0, n);
    array[index] = n
 }

这里是我的假设：正常插入N个数字当然严格来说是N个，但是随机位置的碰撞会产生多少代价呢？对于每个 n，其冲突率增加 0、1/n、2/n .... n-1/n，因此预期的插入尝试次数将是 1、2、3 .. n-1，这是 O (n)，所以总时间复杂度为 O(n^2)，这是平均成本吗？但是哇，这真的很糟糕，我说的对吗？

那么，如果我进行线性搜索而不是继续尝试生成随机数，会发生什么情况？它的最坏情况显然是O(n^2>，但我不知道如何分析它的平均情况，这取决于平均输入分布？

Answer 1

第 i 步的预期插入尝试次数是

sum_{t=0}^infinity (1-i/n)^t * (n-i)/n * t 
= (n-i)/n * i/n * (1-i/n)^{-2}
= i/(n-i)

对 i 求和得到

sum_{i=0}^{n-1} i/(n-1)
>= sum_{i=n/2}^n i / (n-i) 
>= n/2 sum_{x=1}^n/2 1/x
>= n/2 * log(n) + O(n)

和

sum_{i=0}^{n-1} i/(n-i)
<= n * sum _{x=1}^n 1/x
<= n * log(n) + O(n)

所以你得到的是 n*log(n) 作为渐近复杂度。这并没有你担心的那么糟糕。

关于进行线性搜索，我不知道您将如何在保持数组随机的情况下进行搜索。如果你真的想要一个高效的算法来洗牌你的数组，你应该看看 Fisher-Yates shuffle。

Answer 2

首先考虑内循环。当数组中已有 i 个值时，我们预计什么时候会取得第一次成功（找到空缺职位）？为此，我们使用 geometric distribution:

Pr(X = k) = (1-p)^{k-1} p

其中 p 是尝试成功的概率。这里 p 是数组索引尚未填充的概率。有 i 个职位空缺，所以 p = (1 - (i/n)) = ((n - i)/n).

根据 wiki，几何分布的期望值是 1/p = 1 / ((n-i)/n) = n/(n-i)。因此，当数组中有 i 项时，我们应该期望在内循环中进行 (n / (n - i)) 次尝试。

为了填充数组，我们在数组中有 i=0..n-1 项时插入一个新值。我们预计总的尝试次数是总和：

sum_{i=0,n-1} n/(n-i)
= n * sum_{i=0,n-1}(1/(n-i))
= n * sum_{i=0,n-1}(1/(n-i))
= n * (1/n + 1/(n-1) + ... + 1/1)
= n * (1/1 + ... + 1/(n-1) + 1/n)
= n * sum_{i=1,n}(1/i)

n 乘以 nth harmonic number，大约为 ln(n) + gamma，其中 gamma 是常数。所以总体来说，尝试的次数大约是n * (ln(n) + gamma)，也就是O(nlog n)。请记住，这只是期望值，没有真正的上限，因为内循环是随机的；它可能永远找不到空位。

随机数组插入的时间复杂度

time complexity of randomized array insertion

arrays

random

algorithm

insert

time-complexity