use*_*834 4 sorting algorithm time-complexity decision-tree data-structures
这是2016年的入学考试问题：
我们有N个球，其权重不同且未知，标记为1到n。我们得到了两盘式天平，并希望将其用于成对称重这些球，并将它们写在纸上，以便对所有这些球进行分类。在最坏的情况下，需要进行多少次称重操作？选择最佳答案。
a）Ceil [？n log 2 n？]
b）地板[？n log 2 n？]
c）n ??? 1
d）Ceil [？log 2 n !?]
根据答案纸，正确的解决方案是：Ceil [？log 2 n !?]
我的问题是：如何实现此解决方案（此算法如何工作，是否存在伪代码？）？
如果您查看Merge-Sort中的比较数，您会在那找到我的答案，争辩说mergesort（已知具有良好的渐近行为）的比较总数为
n？log 2 n？？2 ？log 2 n？+1
当然n？log 2 n？=？n log 2 n？和2 ？log 2 n？？n是n吗？1确认答案（a）为上限。
（b）上限是否更严格？如果写？log 2 n？= log 2 n + d大约为0？d <1那么您得到
n（log 2 n + d）？2 d n + 1 = n（log 2 n + d？2 d）+ 1 =（n log 2 n）+ n（d？2 d + 1 / n）
并且如果写m：=？log 2 n？n = 2 m ??? d，最后一个括号变为（d？2 d + 2 d ??? m）。
将其绘制为m的某些值表明，对于整数m？1这将非常可能为零。对于n = 1，您将得到m = 0，这意味着d = 0，因此整个括号变为零。因此，当您确定证明的细节时，这将表明（b）确实是mergesort的上限。
怎么样（三）？n？=？3有一个简单的反例。如果您知道球1轻于2且小于3，则不会告诉您如何对2和3进行排序。您可以通过将1与2和3进行比较来表明您没有选择次优算法，由于问题的对称性，这是一种普遍情况。因此（c）不是上限。可以下限吗？当然，即使要确认已经订购了这些球，也必须对每对连续球进行称重，这样才能进行n ??? 1比较。即使使用最佳算法，也无法比猜测正确的顺序然后确认您的猜测更好。
（d）下限是否更严格？再次表明，该图至少与（c）一样大，除了没有整数值的小区域。因此，如果它是一个下限，它将更严格。现在考虑一个决策树。排序这n个球的每种算法都可以写成二进制决策树：您比较给定节点中命名的两个球，并根据比较结果继续进行以下两个可能步骤之一。该决策树必须具有n！叶子，因为每个排列都必须是不同的叶子，所以一旦到达叶子，您就知道确切的排列。和带有n的二叉树！叶子的深度必须至少为“ log 2 n！”。是的，这也是一个下限。
总结一下您拥有的所有这些内容（c）？（d）？X ？（b）？（a），其中x表示比较数，最佳算法将需要对所有球排序。正如马克·迪金森（Mark Dickinson）的评论所指出的那样，关于OEIS的A036604给出了几个n的明确下界，并且对于n？=？12，不等式（d）<x是严格的。因此，（d）也没有准确描述最佳算法。
顺便说一句（并回答您的“该算法是如何工作的”），至少在理论上，找到给定n的最佳算法是相当容易的：为这些n计算所有可能的决策树！排序，然后选择深度最小的一种。当然，这种方法很快变得不切实际。
现在我们知道，没有一个答案可以给出最佳排序算法的正确计数，哪个答案是“最佳”？这在很大程度上取决于上下文。在许多应用中，了解最坏时间行为的上限比了解下限更有价值，因此（b）优于（d）。但是显然，创建解决方案表的人有不同的看法，并选择了（d），这是因为它更接近于最佳值（我假设但尚未证明），或者因为下限对手头的应用程序更有用。如果您愿意，您可能会以问题的范围没有充分定义“最佳”为由对整个问题提出质疑。