排序算法精确案例概率分析
sorting algorithm exact case probability analysis
我正在为一项学校作业查看此问题。我在网上找不到任何 material 可以很好地解释这一点，所以我正在寻找解决此类问题的通用方法。如果您不想给出答案，请给我一个解释或指向一些资源：
假设您要合并两个排序列表，每个列表的大小为 m。请注意，这将在最坏的情况下恰好使用 2m − 1 次比较（因为在某个时候一个列表将变为空而另一个列表不会），而在最好的情况下恰好使用 m 次比较。
假设列表在以下意义上是随机的：您正在对随机数组（或更准确地说是随机排列）执行合并排序，并且您将要进行合并。
(a) 该算法恰好进行 2m − 1 次比较的概率是多少。证明合法。简化。
(b) 该算法恰好进行 2m − 2 次比较的概率是多少。证明合法。简化。
(c) 该算法恰好进行 m 次比较的概率是多少。证明合法。简化。
我不太清楚如何处理这样的概率问题。我试图列出确切的安排数量，但事实证明这是有效的。 a)部分我得到的答案是m!/(m^m)，我不确定，我也想不通第二部分。
我们将您要合并的两个列表称为 A 和 B。为了清楚起见，我们假设排序顺序是升序的，并且不失一般性，假设合并后的数组包含数字 1， 2, 3, ..., 2 米。准确地说，我们假设 "random permutation" 表示 "all permutations are equally likely".
如果其中一个列表（B，比方说）在A耗尽时剩下k个元素，那么B[m-k]一定比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).
A 和 B 一般有 (2m 选择 m) 种可能性，所以总的来说，合并后 B 中剩下 k 个元素的概率是 (2m-k-1 选择 m-1) / (2m 选择 m ).
A 或 B 中剩余 k>0 个元素的概率是其两倍。
如果A或B中还剩k个元素，则总的比较次数为2m-k。所以我们可以回答您的问题：
- (a) 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-2 比较发生在 2m 和 2m-1 出现在同一个数组中，而 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选择米）。
我正在为一项学校作业查看此问题。我在网上找不到任何 material 可以很好地解释这一点，所以我正在寻找解决此类问题的通用方法。如果您不想给出答案，请给我一个解释或指向一些资源：
假设您要合并两个排序列表，每个列表的大小为 m。请注意，这将在最坏的情况下恰好使用 2m − 1 次比较（因为在某个时候一个列表将变为空而另一个列表不会），而在最好的情况下恰好使用 m 次比较。 假设列表在以下意义上是随机的：您正在对随机数组（或更准确地说是随机排列）执行合并排序，并且您将要进行合并。
(a) 该算法恰好进行 2m − 1 次比较的概率是多少。证明合法。简化。
(b) 该算法恰好进行 2m − 2 次比较的概率是多少。证明合法。简化。
(c) 该算法恰好进行 m 次比较的概率是多少。证明合法。简化。
我不太清楚如何处理这样的概率问题。我试图列出确切的安排数量，但事实证明这是有效的。 a)部分我得到的答案是m!/(m^m)，我不确定，我也想不通第二部分。
我们将您要合并的两个列表称为 A 和 B。为了清楚起见，我们假设排序顺序是升序的，并且不失一般性，假设合并后的数组包含数字 1， 2, 3, ..., 2 米。准确地说，我们假设 "random permutation" 表示 "all permutations are equally likely".
如果其中一个列表（B，比方说）在A耗尽时剩下k个元素，那么B[m-k]一定比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).
A 和 B 一般有 (2m 选择 m) 种可能性，所以总的来说，合并后 B 中剩下 k 个元素的概率是 (2m-k-1 选择 m-1) / (2m 选择 m ).
A 或 B 中剩余 k>0 个元素的概率是其两倍。
如果A或B中还剩k个元素，则总的比较次数为2m-k。所以我们可以回答您的问题：
- (a) 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-2 比较发生在 2m 和 2m-1 出现在同一个数组中，而 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选择米）。