Временная сложность этой реализации подсчета сортировки

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 - это постоянные затраты, в противном случае мы должны сказать, что + = является амортизированной константой, и поэтому результат приходит с этим предупреждением).