这种计数排序实现的时间复杂度

Question

我必须确定给定计数排序代码的时间复杂度。我知道计数排序应该是O(n+k)，但是我就是看不出这个函数是O(n+k)的，因为在第二个for循环中有一个for循环。

def counting_sort(array, k): # k is max(array)

    count = (k+1) * [0]  
    sorted = []
    for i in array:
        count[i] += 1
    for i in range(len(count)):
        if count[i] != 0:
            sorted += [i for j in range(count[i])]
    return sorted

如果元素是唯一的，最坏的情况不是n+k^2吗？

Answer 1

第一个循环

for i in array:
    count[i] += 1

进行n次迭代，对于第二个循环，表示在列表理解的最坏情况下执行的指令的数量：

i for j in range(count[i]) #

是count[i]，并且所有count[i]的总和等于n。

        if count[i] != 0:

被执行k次，在最坏的情况下，

sorted +=...

也做了k次。把所有这些加起来，你就得到了O(n+k)

(假设sorted的+=是恒定成本，否则我们必须说+=是摊销常量，因此结果伴随着该警告)。