我的目标是找到列表中任何两个元素之间的最小差异。我编写了以下代码,但我想知道在时间复杂度方面是否有更有效的方法。
def minimumAbsoluteDifference(arr):
arr.sort()
min_diff = abs(arr[0] - arr[1])
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if abs(arr[i] - arr[j]) < min_diff:
min_diff = abs(arr[i] - arr[j])
else:
continue
return min_dif
实际上,如果仔细看,您会发现对列表进行排序后不需要使用两个循环。您可以通过以下方式直接执行-
def minimumAbsoluteDifference(arr):
arr.sort()
min_diff = 10**10 #Initilising to an huge value
for i in range(len(arr)-1):
if arr[i+1] - arr[i] < min_diff:
min_diff = arr[i+1] - arr[i]
return min_dif
一旦对列表进行排序,最小绝对差的潜在候选者只是相邻元素。
一旦远离相邻元素,绝对差必然会增加
例如,考虑排序列表为lst = [2,3,5,8,15]
。我们开始比较2和3。一旦比较它们,就不必比较2和5,因为它们之间的差异将始终大于相邻元素。同样,我们只比较3 and 5
,不比较3 and 8
或其他任何带有3的元素。
因此,此修改后的解决方案将以O(nLogn)
时间复杂度工作,这比使用2个循环O(n^2)
更快。
希望这会有所帮助!
一旦有了排序数组,就不需要扫描所有对:显然,元素i和元素i + 1之间的差异将小于或等于(i,i + 2)元素之间的差异。一种更快的方法是检查每两个相邻元素之间的差异:
def minimumAbsoluteDifference(arr):
# assumption: there is more then one element in array
arr.sort()
min_diff = arr[1] - arr[0]
for i in range(1, len(arr)):
curr_diff = arr[i] - arr[i-1]
min_diff = min(min_diff, curr_diff)
return min_diff
遍历为O(n)
的数组。每次此代码选择电流差和到目前为止找到的最小差之间的最小值。arr.sort
取O(nlogn)
,所以总时间复杂度为O(nlogn)
。您的原始代码为必填项O(n^2)
最简单的方法:
def minimumAbsoluteDifference(arr):
arr.sort()
min_diff = float('inf') # initiating with infinity value
for i in range(2, len(arr)): # start from the second element
min_diff = min(min_diff, abs(arr[i] - arr[i-1])) # use the built-in minimum python method
return min_dif