時間複雜度

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。