Какова временная сложность этого алгоритма сортировки частот? - PullRequest
Новая
       6

Какова временная сложность этого алгоритма сортировки частот?

0 голосов
/ 07 марта 2020 
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, 1, 3, 2, 1, 4, 2, 3, 2, 1], 0, 7), это выход [1 , 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7] Где MX - максимум, а MN - минимальное число в массиве, поэтому, следовательно, сложность времени O (N)?

1 Ответ

0 голосов
/ 07 марта 2020

Сложность вашего кода: O (N + K), где N - количество элементов, а K - диапазон ваших чисел [мин., Макс.]. Это потому, что вы будете l oop по каждому числу i в диапазоне (K) + для каждого числа i, вы добавите count_freq[i] элементов к результату. суммируя все числа в count_freq, вы получите N, которое является числом элементов.

...