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

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是恒定成本，否则我们必须说+ =是摊销常数，因此结果伴随着警告）。