假设我有不同(可能是随机)权重的对象。对象被标记为从n1,并且不进行排序。
我打算根据对象的权重对其进行排序。我唯一的工具是一个有两个盘子的刻度盘,我可以用它来比较一对一对的物体,并把两对的结果记录在日志上我想知道,在最坏的情况下,我要用秤做多少次称重操作。
algorithm - 我们必须执行一次操作来对“n”个项目进行排序的次数-LMLPHP
我仔细想了想,我想我做称重操作的次数是

(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))是任何最优排序算法比较次数的最坏情况下界。

10-01 06:53
查看更多