Bogosort的平均時間複雜度是多少？

我聽說Bogosort的行爲沒有上限。不過，我從來沒有聽到有人談論它的平均行爲。這是一個愚蠢的任務，但不切實際的思想實驗仍然是一種很好的做法，儘管它們可能不切實際。Bogosort的平均時間複雜度是多少？

我想說的是，每學期是：

P(x==y)*P(x!=y)^(k-1) 
    = 1/n * (1-1/n)^(k-1) 
    = (n-1)^(k-1)/n^k

其中k爲0和更大。我知道這個系列是收斂的，所以我們可以找到一個有限到有限的複雜關係（不像最壞的情況，其他人試圖寫成O（無窮大），因爲試圖在無限功能）

任何人都可以解決這個問題嗎？或者，這是一種複雜性，如果沒有無限的總和，就不可能寫出或近似？

來源

2013-11-09 John P

它就在維基百科頁面上...... – delnan

你是對的，當然，我不認爲會有一個廣泛的頁面，或者我只是谷歌搜索它。 –

有一個更直接的方法來做到這一點。 Bogosort通過隨機排列元素來工作，並在結果排列排序時終止。有n！數組元素的可能排列（假設它們都是不同的），並且只有其中一個排序。因此，輸入的均勻隨機置換排序的概率爲1/n！。使用標準的概率結果，這意味着，根據預期，在我們生成排序的排列之前將發生的排列的數量是n !.這意味着Bogosort的預期運行時間爲Θ（n＆middot; n！），因爲我們執行n！隨機排列，每個排序需要花費時間Θ（n）做（和Θ（n）檢查時間）。

如果你想在這個題目正式的數學論述，認爲在看文章Sorting the Slow Way，其中分析BOGO排序等相關種類。

希望這會有所幫助！

來源

2013-11-10 05:09:34 templatetypedef

平均需要O（1）次才能確定隨機排列沒有排序。雖然排列本身仍然是O（n），但如果你做了一個Fisher Yates，你可以在第一個反演出現在第k步時儘早放棄排列。這又讓你在O（1）處產生並拒絕一個部分的，沒有排序的排列。 –

@ rrenaud-這是一個很好的觀點。我假設我們並沒有試圖優化bogosort，因爲它是bogosort。 :-) – templatetypedef

Bogosort的平均時間複雜度是多少？

回答

相關問題