下面的函数是O(n)时间和O(1)空间吗，其中n = |A|？

Question

def firstMissingPositive(self, A):
    least = 1024*1024*1024
    # worst case n ops
    for i in A:
        if i < least and i > 0:
            least = i
    if least > 1:
        return 1
    else:
        # should be O(n)
        A_set = set(A)
        # worst case n ops again
        while True:
            least += 1
            if least not in A_set:
                return least

我问这个问题只是因为它对于给定的问题来说太简单了，这里的大多数人可能在Leetcode或类似的地方看到过。在Python的set或dict实现中有什么我不知道的吗？根据我的理解，查找应该是O（1），将列表转换为集合应该是O（n）。你知道吗

Answer 1

它不是O(1)空间，而是O(n)空间，因为您需要构建集合。你知道吗

至于时间，根据the Python wiki，set containment需要O(n)最坏的情况。所以你的算法就是O(n^2)。注意这是最坏的情况-集合包含的平均时间是O(1)，因此算法的平均时间复杂度确实是O(n)。你知道吗

通过使用有序集，可以将最坏情况降到O(n log n)，但是平均时间也将是O(n log n)。你知道吗