python - 这个函数是 O(N+M) 还是 O(N*M)？

Question

def solution(M, A):
    result = [0] * M
    maxCount = 0
    setAll = 0

    for i in range(0,len(A)):
        if (A[i] == M + 1):
            setAll += maxCount
            maxCount = 0
            result = [0] * M
        else:
            result[A[i] - 1] += 1

            if (result[A[i] - 1] > maxCount):
                maxCount = result[A[i] - 1]

    for j in range(0,len(result)):
        result[j] += setAll

    return result


A = [ 1, 1, 1, 1, 2, 3] 
M = 2

print solution(M, A) # result = [ 4, 4 ]


A = [ 1, 2, 2, 4, 1, 1] 
M = 3

print solution(M, A) # result = [ 4, 2, 2 ]

据我计算，solution() 循环 AN 次，然后循环结果 M 次，因此循环 N+M。但是，在线测试说它是N * M，让我很难过。

Answer 1

它是O(M + N)；这里没有嵌套循环。对于较大的数量，这可以降低成本；渐近地，较小的循环无关紧要，使其O(N).

首先循环遍历A元素（N迭代），然后分别循环遍历M元素。

Answer 2

是的，因为给定输入O(N)有循环。出于时间复杂性的目的，这减少到两者中的较大者（假设是），因为我们只取最重要的项。如果第二个循环嵌套在第一个循环内。N + MN, MNO(N*M)