Нижняя граница сортировки на основе сравнения значений n в диапазоне от 1 до k

Question

Можем ли мы добиться большего успеха, чем O (n lg n) времени выполнения алгоритма на основе сравнения, когда все значения находятся в диапазоне от 1 до k, где k

Счетная сортировка и сортировка по основанию не являются алгоритмами сравнения и не допускаются. При анализе дерева решений кажется, что существует k ^ n возможных перестановок. Есть 2 ^ h листьев, поэтому должна быть возможность решить проблему за O (n lg k) времени с помощью алгоритма сортировки на основе сравнения .

Пожалуйста, не дайте алгоритм сортировки, не основанный на сравнении, для решения этой проблемы, вся сортировка должна основываться на сравнении двух элементов. Спасибо!

Answer 1

Это может быть легко сделано в указанной вами области. Постройте двоичное дерево из k листьев и добавьте значение счетчика на каждом листе. Обработка каждого элемента (добавление его или увеличение счетчика) будет O (lg k), если используется подходящий алгоритм балансировки, поэтому все они будут O (n lg k). Восстановление списка тогда будет O (n).

Answer 2

Хорошо, если вы настаиваете, что хотите сравнения.

У вас есть k элементов. Итак, сохраните древовидную структуру, которая будет содержать все элементы.

Пройдите по списку предметов, каждый раз добавляйте предмет в дерево. Если элемент уже находится в дереве, просто увеличьте счетчик в этом узле. (или если вы хотите фактические элементы, вы можете сохранить список в каждом узле)

В дереве будет не более k предметов.

в конце обойдите дерево по порядку и добавьте элементы обратно в правильном порядке (при добавлении суммы, находящейся в счетчике узла).

Сложность: O (nlogk)

Answer 3

Да, вы можете использовать массив размером k.(Без сравнений)

Каждая ячейка i будет содержать список.
перейти по исходному массиву, поместить каждый элемент в список правой ячейки.

Перейти по второму массивуи вытащите их, верните их в правильном порядке.

O (n)