隨機選擇樞軸的優勢

在快速排序中，我們可以用不同方式選擇樞軸值。隨機選擇一個樞軸值就是其中之一。它說，當我們隨機選擇樞軸值時，它最大限度地減少了有O（n^2）的機會。任何人都可以解釋它是如何發生的？有什麼缺點嗎？隨機選擇樞軸的優勢

2013-02-08 Rhokai

如果在所有可能的輸入（置換）上對期望值進行平均，那麼隨機和非隨機選擇都會產生一個算法，其期望運行時間爲Theta（n * log（n））。

實際上，並非所有的輸入排列都是同等可能的。特別是當你先選擇給出Theta（n^2）複雜性時，你經常會得到排序或接近排序的數組。最重要的是，如果您的挑選算法是確定性的，攻擊者可以制定一個令人討厭的排列，使您的算法保持二次方，從而實現拒絕服務。

選擇隨機元素作爲樞軸防範這些非隨機情況。

2013-02-08 08:00:34

此答案超載期限預計運行時間。一種情況實際上是關於平均情況複雜性（即假設輸入是隨機的並且可能性相同）並且與問題無關，另一種情況是更恰當地使用該術語：無論輸入如何，只有算法的隨機選擇會影響運行時如尼莫的答案）。 – 2013-02-08 19:11:09

@Confusius確實。一點不準確可以節省大量的解釋（但你可以做得過分）。 –

有一個數學證明，隨機數據透視的預期運行時間是Theta（n logn）。

wiki page有一個部分。

2013-02-08 06:23:46 FoundNemo

回答