Python - 时间复杂度 O(N**2)

Question

谁能告诉我在下面的代码中，我们得到 O(N**2):

def solution(X, A):
    assistant = list(range(1, X+1))
    assistant_sum = sum(assistant)
    helper = set()
    if X not in A:
        return -1
    if A.count(A[0]) == len(A):
        if A[0] == 1:
            return 0
        return -1
    for y in A:
        helper.add(y)
    sorted_helper = sorted(list(helper))
    if sum(sorted_helper[0:X]) == assistant_sum:
        helper = set()
    for index, i in enumerate(A):
        try:
            helper.add(i)
            if len(list(helper)[0:X]) == len(assistant) and int((list(helper)[0]+list(helper)[X-1])/2.0*len(helper)) == assistant_sum:
                return index
        except IndexError:
            pass
    else:
        return -1

有没有办法在线查看时间复杂度？ 感谢您的帮助！

Answer 1

helper 是一个可以与 A 长度相同的集合。在你的 for 循环中 for index, i in enumerate(A) 然后你调用 list(helper)

A的长度为N，list(helper)为O(N)，for index, i in enumerate(A)为O(N)。

O(N) 循环中的 O(N) 语句给出 O(N**2)