从列表中删除重复项的算法的三种不同实现的渐近界（O vsΘ）的选择

Question

我想弄清楚时间复杂性的渐近符号。我知道big-O是上界，θ是紧界，但我不知道什么时候用哪个，为什么有时一个给定而不是另一个

具体来说，对于下面给出的同一算法的三种实现，作者将时间复杂度分别描述为O（n²）、}（nlogn）和}（n）

我想了解专家在做这些任务时，在这些问题上的想法。为什么第一个是大O，而另外两个是θ，为什么最后一个提到平均情况，而另外两个没有

非常感谢您的帮助

def RemoveDuplicates(A):
    m = 0
    for i in range(0, len(A)):
        if (not elem(A, m, A[i])):
            A[m] = A[i]
            m += 1
    return m


def elem(A, n, e):
    for i in range(0, n):
        if (A[i] == e):
            return 1
    return 0


A = [54, 26, 93, 54, 77, 31, 44, 55, 20]
RemoveDuplicates(A)
print(A)
# Time Complexity O(n²)


def RemoveDuplicates(A):
    A.sort()
    print(A)
    j = 0
    for i in range(1, len(A)):
        if (A[j] != A[i]):
            j += 1
            A[j] = A[i]

    print(A[:j + 1])


A = [54, 31, 93, 54, 77, 31, 44, 55, 93]
RemoveDuplicates(A)
# Time Complexity: Ө(nlogn) 

A = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']
unique = []
helperSet = set()
for x in A:
    if x not in helperSet:
        unique.append(x)
        helperSet.add(x)

print(A)
print(unique)
# Time Complexity: Ө(n) on average

Answer 1

对于第一种情况，老师写O（n²）而不是ㄊ（n²），因为有些情况下它可能比n²快；例如，如果数组A只填充了一个唯一元素的副本，例如A=[3,3,3,3,3,3,3,3]，那么在这种特殊情况下，算法将执行n次运算，而不是n²。但它永远不会超过n²

对于第二种情况，算法的复杂度将与A.sort()的复杂度相同；接下来的for循环是O（n），它比A.sort()快。因此，该算法的复杂性是数组排序的复杂性。老师认为这始终是n log（n）。这并不完全正确-例如，在CPython中.sort()的实现是这样的，如果您尝试对已经排序的数组进行排序，那么它会更快

对于第三种情况，如果我们假设helperSet.add(x)的时间复杂度为O（1），那么算法是}（n），因为它只是一个For循环。现在，如果您查看set.add的文档，您会看到类似“set.add几乎总是O（1），除非您非常不走运或受到攻击”（这与哈希函数和冲突概率有关，因为集合通常作为哈希映射实现）。所以老师把它简化为“平均来说，set.add是O（1），所以平均来说，我们的算法是}（n）”