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

2024-06-15 02:57:30 发布

您现在位置:Python中文网/ 问答频道 /正文

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)。你知道吗


Tags: andinselfforreturnifdefelse
1条回答
网友
1楼 · 发布于 2024-06-15 02:57:30

它不是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)。你知道吗

相关问题 更多 >