鉴于未进行的$ N $项目列表，平均需要多少随机比较才能对列表进行排序？

Question

有一个未蚀刻的 $ n $ 项目 $ x_1，\ ldots，x_n $ 。直到您可以对列表进行排序，您将获得其中一个 $ {n \选择2} $ 可能的二进制比较，随机（用替换）。

平均来，您需要如何对列表进行排序的这些随机比较？

一些后续问题：

1. 所需比较数量的分布是什么样的？
2. 如果使用 $ k $ - k $ ，而不是二进制文件，则答案是什么是答案。
3. 如果在没有替换的情况下进行比较（即，两次也是相同的比较）？
4. 给出了一组比较，如何检查列表是否排序？我几乎确定了答案是建立一个愚蠢和拓扑排序，但我只是想确认。

一个精确的答案会很好，但是一个大 $ o $ 答案也很好，我想。

Answer 1

assympotally，您需要 $ \ theta（n ^ 2 \ log n）$ 比较。

假设 $ x _ {（1）}，\ dots，x _ {（n）} $ 表示按排序顺序的元素。然后，如果您没有看到 $ x {（1）} $ 和 $ x {（2）}之间的比较。 $ ，您将无法判断它们应该出现的顺序。每对相邻元素都是如此。因此，存在 $ n-1 $ 优惠券（每个相邻的元素的一个元素），您需要收集它们。基于优惠券收集器问题，我们知道您将需要 $ \ theta（n \ log n）$ 随机选择的优惠券，然后我们收集了所有这些优惠券。每次观察都有一个 $ 2 / n $ 作为优惠券的可能性，总共需要 $ \ theta（n ^ 2 \ log n）$ 观察在我们收集所有优惠券之前。如果我们收集所有优惠券，我们可以对 $ x $ '进行排序;如果我们缺少任何优惠券，我们就无法对它们进行排序。

随后的问题归结为关于优惠券收集器问题的事实，您可以使用维基百科上的尾部边界来绑定有关分发的信息。

如果在没有替换的情况下选择比较，则需要 $ \ theta（n ^ 2）$ 观察。

检查列表是否可排序的合理方式是进行拓扑排序，然后检查您在拓扑排序顺序中观察到每对相邻项目之间的比较。