这个函数是O(N + M)还是O(N * M)? [英] Is this function O(N+M) or O(N*M)?

问题描述

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()循环N次，然后循环结果M次，因此N + M. 但是，一项在线测试却说它是N * M，这让我很沮丧.

By my count, solution() loops through A N times and then loops result M times thus N+M. However, an online test said that it was instead N*M, leaving me stumped.

推荐答案

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

It is O(M + N); there are no nested loops here. This can be reduced to the cost for the larger number; asymptotically, the smaller loop is not going to matter, making it O(N).

首先循环遍历A元素(N迭代)，然后分别循环遍历M元素.

First you loop over A elements (N iterations), then separately you loop over M elements.

这篇关于这个函数是O(N + M)还是O(N * M)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！