Анализ сложности худшего во время выполнения «Top K самых частых элементов»

Question

Описание проблемы:

Учитывая непустой список слов, вернуть k наиболее часто встречающихся элементов.

Ваш ответ должен быть отсортирован по частоте от самой высокой к самой низкой.Если два слова имеют одинаковую частоту, то слово с более низким алфавитным порядком идет первым.

Например: Пример 1: Ввод: ["i", "love", "stackoverflow", "i", "love "," coding "], k = 2 Вывод: [" i "," love "] Объяснение:" i "и" love "- два наиболее часто встречающихся слова.Обратите внимание, что «i» стоит перед «любовью» из-за более низкого алфавитного порядка.

Мое решение Python с использованием частотных интервалов:

def topKFrequent(words, k):       
    wordCount = collections.Counter(words)
    freq = [[] for i in range(len(words) + 1)]
    res = []
    for word, count in wordCount.items():
        freq[count].append(word)
    for i in range(len(freq) - 1, 0, -1):
        if k == 0:
            break
        elif k >= len(freq[i]):
            res.extend(sorted(freq[i]))
            k -= len(freq[i])
        else:
            res.extend(sorted(freq[i])[:k])
            break
    return res

Теперь я утверждаю, чтовыполняется в O (nlogn), игнорируя инициализацию Counter и инициализацию freq, каждый из которых O (n), в последнем цикле в худшем случае будет один блок со всеми словами в нем (каждое слово появляется ровно один раз), поэтому мы в итоге просто сортируем этот сегмент, который является nlog (n).

Является ли приведенный выше корректный интуитивный анализ?

Answer 1

Да, ваш анализ верен. Если у вас есть n слов, то ваши шаги инициализации выполняются в O(n). Затем ваш цикл for выполняет O(m log m) сортировку для каждого из j разделов. Вот доказательство:

Пусть L будет списком n элементов. Разделите L на j различных разделов, каждый из которых содержит n_1, ..., n_j элементов. Ясно, что n_1 + ... + n_j = n и 1 <= j <= n </strong>.

Мы можем игнорировать итерации, которые не обрабатывают какие-либо элементы, поскольку они ограничены константными n операциями. Таким образом, цикл for работает на j итерациях, и в каждой из них работает O (n_i log n_i) . Таким образом, каждая из этих итераций ограничена C_i n_i log n_i для подходящих констант C_i . Тогда общая работа составит C_1 n_1 log n_1 + ... + C_j n_j log n_j . Предположим, что K является самым большим из C_i . Тогда это ограничено сверху как K n_1 log n + ... + K n_j log n = K (n_1 + ... + n_j) log n = K n log n . Поэтому цикл работает в O (n log n) времени.

Замечу, что существует алгоритм n log k, который включает в себя использование минимальной кучи, в которой вы сохраняете не более k элементов ...