Как я могу отсортировать данную запись в разное время выполнения - O (n) и O (nlogk), где k - это отдельные значения для последовательности n с парами ключ-значение?

Question

Моя заданная последовательность выглядит так

<product, quantity>

<milk, 2>, <bread, 3>, <eggs, 3>, <sugar, 2>, <apples, 4>, <berries, 4>
Here I have my n value as 6 and k as 3 (3 distinct values - 2, 3, 4).

Моя отсортированная последовательность должна быть такой.Сортировка в порядке возрастания значений ключей

<milk, 2>, <sugar, 2>,  <bread, 3>, <eggs, 3>, <apples, 4>, <berries, 4>

Какие алгоритмы можно использовать для сортировки за два времени работы?1. O (n) 2. O (nlogk)

Answer 1

Я только начал изучать алгоритмы, так что поправьте меня, если я ошибаюсь.Я думаю, что мы можем использовать красное дерево или древовидную карту для сортировки ключа, пары значений во время выполнения O (n), а затем пройти через пару ключ-значение, чтобы отобразить отличные значения k во время выполнения O (log k).Таким образом, общее время работы этого алгоритма будет равно n * log k = O (n log k).