假设我有不同(可能是随机)权重的对象。对象被标记为从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))
是任何最优排序算法比较次数的最坏情况下界。