给定一个未排序的整数数组,不做任何有关数组中数字的假设:
是否可能在O(n)时间内找到差值最小的两个数?
编辑:两个数字a,b之间的差异定义为abs(a-b)
给定一个未排序的整数数组,不做任何有关数组中数字的假设:
是否可能在O(n)时间内找到差值最小的两个数?
编辑:两个数字a,b之间的差异定义为abs(a-b)
我认为你不能在O(n)的时间复杂度内完成这个任务。从我的经验来看,最好的方法是对它们进行排序(时间复杂度为O(n * log n)),然后在排序后的列表中找到相邻对之间的最小差值(这将增加另外的O(n)时间复杂度)。
我能想到的最好方法是使用计数排序数组(可能会合并相等的值),然后进行排序比较--桶排序的时间复杂度为O(n + M)(其中M是不同值的数量)。然而,这需要大量的内存。某种形式的桶或基数排序在时间上处于中间位置,并且在空间上更加高效。
使用基数排序(对于整数是O(n))对列表进行排序,然后迭代并跟踪到目前为止最小的距离。
(我假设您的整数是固定位类型。如果它们可以容纳任意大的数学整数,则基数排序也将是O(n log n)。)
似乎可以在O(n*sqrt(log(log(n)))时间内对无界整数集进行排序。排序后,当然可以轻松地在线性时间内找到最小差异。
但我想不出比这更快的算法。
不行,除非对数字/排序进行假设。
如果给定一个已排序的列表,那么是可能的。
我认为答案是否定的,证明类似于你不能比n lg n更快地排序的证明:你必须比较所有元素,即创建一个比较树,这意味着omega(n lg n)算法。
编辑。好吧,如果你真的想争论,那么问题并没有指明它应该是图灵机还是不是。使用量子计算,您可以在线性时间内完成:)