时间复杂度

Question

所以我不得不插入随机顺序N个元素成尺寸为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个值时，我们什么时候能够获得第一个成功（找到未定位置）？为此，我们使用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，其中的γ是一个常数。总的来说，尝试次数大约为n * (ln(n) + gamma)，即O(nlog n)。请记住，这只是期望，并且由于内部循环是随机的，所以没有真正的上限;它可能永远找不到开放的地方。

Answer 2

插入预期数量的尝试，在步骤我是

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。