假设我有不同（可能是随机）权重的对象。对象被标记为从n到1，并且不进行排序。
我打算根据对象的权重对其进行排序。我唯一的工具是一个有两个盘子的刻度盘，我可以用它来比较一对一对的物体，并把两对的结果记录在日志上我想知道，在最坏的情况下，我要用秤做多少次称重操作。
我仔细想了想，我想我做称重操作的次数是
(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0
因此，结果将是
n。因此，大O将n但我不确定我的计算是否正确。我想知道是否有人能提出这个解决方案是否是错误的。如果是，正确答案是什么。
我的理由是，对于对象编号
(n-1)*n/2，我必须将其与O(n)对象进行比较，然后我将能够记录有多少对象比它重/轻。因此，我将知道对象n在所有对象中的位置。对于
n-1对象，我必须对n对象执行称重操作…对于对象编号n-1我必须对n-2对象执行称重操作。因此，总称重操作可能是：(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0
最佳答案
这是计算机科学的标准结果。您可以使用merge sort执行atΘ(n log(n))比较。
证明没有一种渐近更好的方法是：对象最初可以在n!不同的排列中，一次加权最多可以将可能性的数目减半。因此log(n!) = O(n log(n))是任何最优排序算法比较次数的最坏情况下界。