Понимание временной сложности вложенной сортировки
Я решаю задачу LeetCode 1636. Сортировка массива по возрастанию частоты:
Дан массив целых чисел
nums, отсортируйте его в порядке возрастания в зависимости от частоты значений. Если несколько значений имеют одинаковую частоту, отсортируйте их в порядке убывания.Вернуть отсортированный массив.
Я написал следующий рабочий код:
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
ddict = Counter(nums)
ddict = dict(sorted(ddict.items(), key=lambda x:(x[1], x[0])))
defDict = defaultdict(list)
res = []
for k, v in ddict.items():
defDict[v].append(k)
del(ddict)
for k, v in defDict.items():
v.sort(reverse=True)
for val in v:
for _ in range(k):
res.append(val)
return res
Я думаю, что его временная сложность равна O(n.(nlog(n)), потому что в худшем случае я сортирую каждый список в defaultdict для каждого ключа.
Но анализ временной сложности в LeetCode, а также инструменты искусственного интеллекта, такие как (nlog (n))?
@nocomment Не могли бы вы объяснить подробнее, что вы имеете в виду под «не жесткой границей»? Вероятно, это пример, где это может быть O(n.(nlog(n)). Я запутался :(
Точно так же, как, например, сортировка слиянием — O(n^3). Эта граница не является неправильной, она просто не жесткая.
Вы имеете в виду трехстороннюю сортировку слиянием @nocomment?
Нет, просто стандартная сортировка слиянием, которая также является O(n log n).
Извините :( Но я не понимаю. У вас есть что-нибудь, на что я могу сослаться? @nocomment
Вероятно, вам следует обратиться к определению обозначения big-O. Сортировка слиянием — это O(n log n) и O(n^3). Это даже O(n^1000). Точно так же, как яблоко, которое стоит менее 1 доллара, также стоит меньше 1000 долларов.
Ответы 1
Сортировка отдельных фрагментов данных по-прежнему будет занимать O(𝑛log𝑛). Например, предположим, что у вас есть ключи 𝑘 в defDict, каждый из которых имеет список (v) со средней длиной 𝑛/𝑘, тогда сортировка каждого из этих v составит сложность O(𝑘 (𝑛/𝑘) log(𝑛/𝑘)), что равно O(𝑛log(𝑛/𝑘)), что не хуже, чем O(𝑛log𝑛).
Обратите внимание, что ваш v уже отсортирован в порядке возрастания до того, как будет выполнен вызов v.sort, и вы могли бы просто поменять v. Поскольку встроенная сортировка Python (timsort) хорошо справляется с такими входными данными, она будет работать за O(𝑘), где 𝑘 — размер v, что означает, что эта часть вашего алгоритма представляет O(𝑛) как временную сложность, что делает начальная сортировка — определяющий шаг в отношении общей временной сложности: O(𝑛log𝑛).
Спасибо, теперь это имеет смысл. Итак, подведем итог: сортировка каждого списка в defDict не вносит существенного вклада в общую временную сложность в худшем случае. Потому что в худшем случае каждый список в defDict будет иметь максимальный размер, равный количеству элементов с одинаковой частотой. Это означает, что максимальный размер любого списка ограничен n (общее количество элементов в числах). Сортировка списка размера m (где m <= n) в худшем случае занимает время O(m log m). Однако, поскольку m всегда меньше или равно n, этот член поглощается доминирующим O(n log n)
На самом деле их сортировка кусков занимает всего лишь линейное время.
@nocomment, правда, поскольку v уже отсортирован в порядке возрастания до того, как будет выполнен вызов sort. Я добавил абзац по этому поводу.
Я бы использовал другое имя для размера v, переопределение n сбивает с толку, особенно когда новое определение не длится даже до конца предложения, так что одно и то же имя имеет два разных значения в одном предложении.
хорошее замечание. Используйте 𝑘 сейчас.
Это O(n.(nlog(n)). Это просто не так уж и сложно.