概率懷疑

Question

我正在處理一個問題 - 有一個最初無序的數字集合。目標是對其進行分類。應該通過對數字進行排序，直到它們落入正確的位置（Yeah，Bogosort'ish :)）。混洗有一個優化，如果在混洗之後，任何元素開始或接近結束的列表落入他們的正確位置，這些元素將被固定，其餘元素將使用上述相同的邏輯進行混洗。問題是要計算排序一組最初無序的數字所需的平均數f，例如6. 我知道它是沿概率線分佈的序列，但不能完全歸零。任何建議/建議在正確的方向或方法將不勝感激。

謝謝

Answer 1

這可以遞歸計算。

• 長度爲0的列表平均需要0次洗牌。 f（0）= 0.
• 長度爲1的列表平均需要0次洗牌。 f（1）= 0.
• 洗牌後長度爲2的列表有幾種可能性：
  • 它已經排序（50％機率）：0洗牌。
  • 它尚未排序（50％機率）：
    • 洗牌排序：1洗牌。
    • 洗牌並沒有幫助，我們需要再試一次：1 + f（2）洗牌。

這CNA可以寫爲：

f(2) = ((1/2) * 0) + ((1/2) * (1/2) * 1) + ((1/2) * (1/2) * (1 + f(2)). 
f(2) = 2/3 

你可以把他們變成你已經解決了小投入以這種方式繼續大投入。