这种频率计数排序算法的时间复杂度是多少

Question

def f(array, mn, mx):
count_freq = [0] * (mx - mn + 1) # to store frequency

for i in array:
count_freq[i] += 1 # populate frequency

result = [] # to be returned
for i in range(mn, mx +1):
result += [i] * count_freq[i]
return result

当调用f([1,4,7,2,3,2,4,2,3,1]，0,7(时，这是输出[1,1,1,1,2,2,2,2,3,4,4,7]其中MX是阵列中的最大值，MN是最小值，因此时间复杂度是O(N(吗？

Answer 1

代码的复杂度为O(N+K(，其中N是元素的数量，K是数字的范围[min，max]。这是因为你将在(K(范围内的每个数字i上循环+对于每个数字i，你将向结果中添加count_freq[i]元素。将count_freq中的所有数字相加，得到N，这是元素的数量。