数组中的最小绝对差

Question

您好，我已经用这个解决方案解决了数组中的最小绝对差问题：

min_diff = 99999999
difference = 0  

for i in range(len(arr)):
    for y in range(len(arr)):
        if i != y:
            defference = abs(arr[i] - arr[y])
            if defference < min_diff:
                min_diff = defference
                
return min_diff

所以你可以看到我的解决方案是 O(n2) 并且它给出了超出时间限制的错误所以我复制了另一个解决方案是这样的：

arr = sorted(arr)

# Initialize difference as infinite
diff = 10**20

# Find the min diff by comparing adjacent
# pairs in sorted array
for i in range(n-1):
    if arr[i+1] - arr[i] < diff:
        diff = arr[i+1] - arr[i]

# Return min diff
return diff

正如您所见，它与我的代码具有相同的时间复杂度，所以为什么这件商品可以正常工作，但我没有收到超出时间限制的错误。请告诉我我的代码和我复制的代码有什么区别。

Answer 1

考虑 O(n) 估计值的一种简单方法是计算您有多少嵌套循环。您的代码有两个循环，因此它是“二次”的，100 个元素需要 100^2 = 10,000 个循环。他们有一个循环（“线性”），100 个元素需要大约 100 个循环。

数组中的最小绝对差

Minimum Absolute Difference in an Array

python

arrays