排序算法精确个案概率分析

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）。