减少时间复杂度

Question

我可以优化下面给出的代码的各种方式。

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

Answer 1

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，因为它们之间的差异将始终大于相邻元素。

因此，此修改后的解决方案将以O（nLogn）时间复杂度工作。

Answer 2

def minimumAbsoluteDifference(arr):
   # assumption: there are 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)