Пространственно-временная сложность топ-k частых элементов в массиве

Question

Существует небольшая путаница в отношении сложности времени и пространства для данной задачи:

Если задан массив размером N , вернуть список из лучших K частые элементы.

На основе самого популярного решения:

1. Использовать HashMap размера K с количеством каждой записи в качестве значения.
2. Создайте MaxHeap размером K , пройдя созданную выше HashMap.
3. Вставьте элементы из MaxHeap в список и верните список.

K - количество уникальных элементов на входе.

Пространственно-временная сложность: O (K) и O (K * log (K)

Теперь здесь начинается путаница. Мы знаем, что имеем дело с наихудшей сложностью в приведенном выше примере)анализ. Таким образом, худшее значение K может принять N, когда все элементы в массиве уникальны.

Следовательно, K <= N. Таким образом, O (K) представляется как O (N) ??</strong>

Таким образом, не должны ли сложность пространства и времени быть O (N) и O (N * log (N)) для вышеуказанной проблемы?

Я знаю, что этотехническая, но это беспокоило меня некоторое время. Пожалуйста, сообщите.

Answer 1

Да, вы правы, поскольку K<N, сложность времени для части хэш-карты должна быть O(N).

Но куча содержит только K элементов и имеет временную сложность O(Klog(K)), которая, если ее рассматривать асимптотически, намного больше, чем линейная сложность O(N), и, следовательно, приводит к конечной временной сложности O(Klog(K)).