algorithm - 我们必须执行操作以对 "n"项进行排序的次数

Question

假设我有 n具有不同(可能是随机)权重的对象。这些对象标记自 1至 n , 它们没有排序。

我打算对 n 进行排序物体基于它们的重量。我唯一的工具是一个带有两个盘子的秤，我可以用它来一对对地比较对象，并将对的结果记录在日志上。我在想，在最坏的情况下，我必须通过秤进行多少次称重操作。

我苦思冥想，我觉得我要做称重操作的次数是

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0

因此，结果将是 (n-1)*n/2 .因此大 O 将是 O(n<sup>2</sup>)

但我不确定我的计算是否正确。我想知道是否有人可以建议此解决方案是否错误。如果是，正确答案是什么。

---

我的幕后推理是，对于对象编号 n , 我必须将它与 n-1 进行比较对象，那么我将能够记录有多少对象比它重/轻。因此，我会知道对象的位置 n在所有对象中。

对于对象编号 n-1 , 我必须用 n-2 进行称重操作对象 ... 对象编号 1我必须用 0 进行称重操作对象。因此，总的称重操作可能是:

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0

Answer 1

这是计算机科学中的标准结果。您可以使用 merge sort在 Θ(n log(n)) 执行比较。

没有渐近更好的方法的证明如下:对象可以在n!中。最初的不同排列，一次称重最多可以将可能性的数量减半。所以log<sub>2</sub>(n!) = O(n log<sub>2</sub>(n))是任何最优排序算法的比较次数的最坏情况下限。