O(N)简单Python函数的时间复杂度

Question

我刚接受了Codility演示测试.的问题,我的答案可以在这里看到,但我会在这里贴上我的回答也是如此.我的回复:

def solution(A):
    # write your code in Python 2.7

    retresult = 1; # the smallest integer we can return, if it is not in the array

    A.sort()
    for i in A:
        if i > 0:
            if i==retresult:   retresult += 1 # increment the result since the current result exists in the array
            elif i>retresult:   break # we can go out of the loop since we found a bigger number than our current positive integer result


    return retresult

我的问题是时间复杂性,我希望通过你的回答更好地理解.问题是要求预期的最坏情况时间复杂度是O(N).

我的功能是否具有O(N)时间复杂度？我对数组进行排序的事实是否会增加复杂性,如果是这样的话？

Codility报告(我的回答)

Detected time complexity: 
O(N) or O(N * log(N))

那么,我的功能的复杂性是多少？如果它是O(N*log(N)),我可以做些什么来降低O(N)的复杂性,因为问题表明了？

非常感谢!

ps我的背景阅读准时复杂性来自这篇伟大的帖子.

编辑

在下面的回复以及此处针对此问题描述的答案之后,我想通过对解决方案的考虑来扩展这一点:

basicSolution具有昂贵的时间复杂度,因此不适合进行此Codility测试:

def basicSolution(A):
    # 0(N*log(N) time complexity

    retresult = 1; # the smallest integer we can return, if it is not in the array

    A.sort()
    for i in A:
        if i > 0:
            if i==retresult:   retresult += 1 #increment the result since the current result exists in the array
            elif i>retresult:   break # we can go out of the loop since we found a bigger number than our current positive integer result
        else:
            continue; # negative numbers and 0 don't need any work

    return retresult

hashSolution是我在上面的文章中描述的内容,在"使用散列"段落中.由于我是Python的新手,请告诉我你是否对这段代码有任何改进(虽然它对我的测试用例有效),以及它有多长时间的复杂性？

def hashSolution(A):
    # 0(N) time complexity, I think? but requires 0(N) extra space (requirement states to use 0(N) space

    table = {}

    for i in A:
        if i > 0:
            table[i] = True # collision/duplicate will just overwrite

    for i in range(1,100000+1): # the problem says that the array has a maximum of 100,000 integers
        if not(table.get(i)): return i

    return 1 # default

最后,实际的0(N)解(O(n)时间和O(1)额外空间解)我无法理解.我知道负数/ 0值被推到数组的后面,然后我们有一个正数值的数组.但我不明白findMissingPositive函数 - 有人可以用Python代码/注释来描述这个吗？还是举个例子？我一直试图在Python中完成它,只是无法弄明白:(

Answer 1

它没有,因为你排序A.

Python list.sort()函数使用Timsort(以Tim Peters命名),并且具有O(NlogN)的最坏情况时间复杂度.

您不必对输入进行排序,而是必须迭代它并确定是否通过其他方式丢失了任何整数.我会使用一组range()对象:

def solution(A):
    expected = set(range(1, len(A) + 1))
    for i in A:
        expected.discard(i)
    if not expected:
        # all consecutive digits for len(A) were present, so next is missing
        return len(A) + 1
    return min(expected)

这是O(N); 我们创建一组len(A)(O(N)时间),然后我们循环A,从expected(从O(N)时间删除元素,从集合中移除元素是O(1)),然后测试为expected空(O(1) )时间),最后得到最小元素expected(最多O(N)时间).

因此,我们在上述函数中最多制作3个O(N)时间步,使其成为O(N)解.

这也符合存储要求; 所有使用都是一组大小为N.集合的开销很小,但总是小于N.

您找到的哈希解决方案基于相同的原则,除了它使用字典而不是集合.请注意,字典值从未实际使用过,它们可以设置为True或不存在.我将其重写为:

def hashSolution(A):
    seen = {i for i in A if i > 0}
    if not seen:
        # there were no positive values, so 1 is the first missing.
        return 1
    for i in range(1, 10**5 + 1):
        if i not in seen:
            return i
    # we can never get here because the inputs are limited to integers up to
    # 10k. So either `seen` has a limited number of positive values below
    # 10.000 or none at all.

如果没有正整数,上面的方法可以避免循环到10.000 A.

我和他们之间的区别在于我的开始是一组预期的数字,而他们从一组正值开始A,反转存储和测试.