排序算法精確個案概率分析

Question

我正在爲一個學校任務尋找這個問題。我找不到任何可以解釋這一點的材料，所以我正在尋找一種解決此類問題的通用方法。如果你不想給出答案，請給我一個解釋或指向我一些資源：

假設你正在合併兩個排序列表，每個大小爲m。請注意，在最壞的情況下，這將使用2m-1的比較（因爲在某些時候，一個列表將變爲空白，另一個列表將不會），並且在最好的情況下恰好是m個比較。 假設列表在以下意義上是隨機的：您正在隨機數組上執行合併排序（或更準確地說是隨機排列），並且您將要執行合併。 （a）算法做2m - 1的比較的概率是多少？自圓其說。簡化。 （b）算法做2m - 2的比較的概率是多少？自圓其說。簡化。

（c）該算法是否準確地進行m次比較的概率是多少。自圓其說。簡化。

我不完全知道要處理這樣的概率問題。我試圖列出確切的安排數量，但它被證明是有效的。我得到的第一部分的答案是m！/（m^m），這是我不確定的，我無法弄清楚第二部分。

Answer 1

讓我們調用兩個你正在合併A和B的列表。爲了清楚起見，讓我們假設排序順序是上升的，並且不失一般性，假設合併後的數組包含數字1，2 ，3，...，2m。準確地說，我們假設「隨機排列」意思是「所有排列都是相同的可能性」。

如果其中一個列表（B，比如說）在A被耗盡時剩下k個元素，那麼它肯定是B [mk]大於A中的所有元素。因爲B被排序，所以B必須保持最大來自1，2，...，2m的k個數字。並且不是第（k + 1）個最大的數字，否則當A被耗盡時，B將剩下至少k + 1個元素。

有多少種可能性呢？那麼，A必須包含2m-k以及最小2m-k-1數字的任何（排序的）大小爲m-1的子集。這是（2m-k-1）選擇（m-1）。 （2m選擇m）在A和B中總體上有可能性，因此整體上在合併之後存在B中的k個元素的概率是（2m-k-1選擇m-1）/（2m選擇m） 。

在A或B中剩餘k> 0個元素的概率是它的兩倍。

如果在A或B中剩下k個元素，比較的總數將是2m-k。所以，我們在一個位置，回答你的問題：

• （一）2M-1的比較：K = 1，所以概率是2（2M-2選擇M-1）/（2M選擇M） = m /（2m-1）。 （b）2m-2比較：k = 2，所以概率是2（2m-3選擇m-1）/（2m選擇m）= m /（4m-2）。 （c）m比較：k = m，所以概率是2（m-1選擇m-1）/（2m選擇m）= 2 /（2m選擇m）。

或者一些簡單的理由是，不通過一般情況下，去：

• （a）當2m和2M-1出現在不同的陣列發生2M-1的比較。 2m出現在一個陣列中，所以有m /（2m-1）的機會出現在另一個陣列中。 （b）當2m和2m-1出現在相同的陣列中時，2m-2的比較發生，而另一箇中出現2m-2時，則出現2m-2的比較。這以概率（m-1）（2m-1）* m /（2m-2）= m/2（2m-1）發生。 （c）當m個最大數字出現在同一個數組中時，發生m個比較。只有兩種可能性（A或B必須包含數字m + 1，...，2m），並且（2m選擇m）一般選擇A和B，所以概率爲2 /（2m選擇m）。