这个函数的时间复杂度是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() 循环 A N 次，然后循环结果 M 次，因此总共是 N+M。 但是，一个在线测试表明它实际上是 N*M，这让我感到困惑。

- Skrealin

Answer 1

它的时间复杂度为O(M + N)；这里没有嵌套循环。可以将其简化为更大的数字的成本；在渐进意义下，较小的循环不会起作用，因此时间复杂度为O(N)。

首先，您要遍历A元素（N次迭代），然后单独遍历M元素。

- Martijn Pieters

---

我没有看到嵌套循环... 我错过了什么吗？ - Brad Allred

是的，缺少了单词“no”。 :-P 哎呀！ - Martijn Pieters

我确实看到了一个嵌套循环（有点像）：for i in range(0,len(A)): ... result = [0] * M。创建赋值语句的右侧应该是Theta(M)，这样做N次是Theta(O*N)（最坏情况）。 - Reinstate Monica

Answer 2

这段代码的时间复杂度为O(N)，因为对于给定的输入N, M，有N + M次循环。在时间复杂度的计算中，我们只取最重要的项，即两者之间较大的一个（假设为N）。如果第二个循环被嵌套在第一个循环中，则时间复杂度将变成O(N*M)。

- joews