algorithm - 排序需要多少操作？

Question

这是一道2016年入学考试题:

We have N balls with distinct and unknown weights that have labels 1 to n. We are given a two-pan balance and want to use it for weighting these balls in pairs and writing them on a paper in-order to sort all of these balls. In the worst case, how many weighing operations are need? Choose the best answer.

a) Ceil[ n log₂ n ]
b) Floor[ n log₂ n ]
c) n − 1
d) Ceil[ log₂ n! ]

根据答题卡，正确解为:Ceil[∼log₂ n! ]

我的问题是:这个解决方案是如何实现的(这个算法是如何工作的，有没有伪代码？)？

Answer 1

如果你看Number of Comparisons in Merge-Sort你会在那里找到我的答案，认为合并排序(已知具有良好的渐近行为)的比较总数是

n ⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + 1

当然 n ⌈log₂ n⌉ = ⌈n log₂ n⌉ 和 2^{⌈log₂ n⌉} ≥ n 所以对于 n ≥ 1 这证实了答案 (a) 作为上限。

(b) 是更严格的上限吗？如果你写 ⌈log₂ n⌉ = log₂ n + d 对于一些 0 ≤ d < 1 然后你得到
n (log₂ n + d) − 2^d n + 1 = n (log₂ n + d − 2^d) + 1 = (n log₂ n) + n (d − 2^d + 1/n)
如果你写 m := ⌈log₂ n⌉ 和 n = 2^{m − d} 最后一个括号变成 (d − 2^d + 2^{d − m})。 Plotting this对于 m 的某些值表明对于整数 m ≥ 1 这将非常可能为零。对于 n = 1，您得到 m = 0，这意味着 d = 0，因此整个括号变为零。因此，当您计算出证明的细节时，这将表明 (b) 确实是归并排序的上限。

(c) 怎么样？ n = 3 有一个简单的反例。如果您知道球 1 比 2 轻且小于 3，这不会告诉您如何对 2 和 3 进行排序。您可以证明您不能选择次优的通过将 1 与 2 和 3 进行比较的算法，由于问题的对称性，这是一种普遍情况。所以 (c) 不是上限。它可以是下限吗？当然，即使要确认球已经被订购，您也必须对每一对连续的球进行称重，从而导致进行 n − 1 次比较。即使使用最好的算法，您也不能比猜测正确的顺序然后确认您的猜测做得更好。

(d) 是更严格的下限吗？ Plots再次表明它至少与 (c) 一样大，除了一个没有整数值的小区域。所以如果它是下限，它会更紧。现在想想决策树。对这 n 个球进行排序的每个算法都可以写成二叉决策树:您比较在给定节点中命名的两个球，并根据比较结果继续执行两个可能的后续步骤之一。该决策树必须有 n!叶子，因为每个排列都必须是不同的叶子，所以一旦到达叶子，您就知道确切的排列。和一棵 n! leafs 的深度必须至少为 ⌈log₂ n!⌉。所以是的，这也是一个下限。

总结所有这些你有 (c) ≤ (d) ≤ x ≤ (b) ≤ (a)，其中 x 表示最佳算法需要对所有球进行排序的比较次数。正如 Mark Dickinson 指出的评论，A036604 on OEIS给出一些 n 的明确下界，并且对于 n = 12，不等式 (d) < x 是严格的。所以(d)也没有准确描述最优算法。

顺便说一下(并回答你的“这个算法是如何工作的”)，找到给定 n 的最优算法相当容易，至少在理论上是这样:为这 n 个计算所有可能的决策树!排序，然后选择深度最小的一个。当然，这种方法很快就会变得不切实际。

既然我们知道没有一个答案给出最优排序算法的正确计数，那么哪个答案是“最好的”？这在很大程度上取决于上下文。在许多应用中，了解最坏时间行为的上限比了解下限更有值(value)，因此 (b) 优于 (d)。但显然创建解决方案表的人有不同的意见，并选择了 (d)，要么是因为它更接近最佳值(我假设但尚未证明)，要么是因为下限对手头的应用程序更有用.如果您愿意，您可能会以问题范围内没有充分定义“最佳”为由质疑整个问题。