Можем ли мы улучшить время O (n lg n) для алгоритма на основе сравнения, когда все значения находятся в диапазоне от 1 до k, где k < п.
Сортировка сортировки и сортировка оснований не являются алгоритмами на основе сравнения и запрещены. По анализу дерева решений кажется, что существует k ^ n возможных перестановок. Есть 2 ^ h листьев, поэтому должно быть возможно решить проблему в O (n lg k) time с помощью алгоритма сортировки на основе сравнения.
Пожалуйста, не давайте алгоритм сортировки, основанный на сравнении, для решения этой проблемы, вся сортировка должна основываться на сравнении двух элементов. Спасибо!
Это можно легко сделать в указанной вами связи. Создайте двоичное дерево из k листьев и включите значение счета для каждого листа. Обработка каждого элемента (добавление его или наложение счетчика) будет O (lg k), если вы используете подходящий алгоритм балансировки, поэтому все они будут O (n lg k). Подтверждением списка будет O (n).
Хорошо, если вы настаиваете на необходимости сравнения.
У вас есть элементы k. Итак, сохраните древовидную структуру, которая будет содержать все элементы.
Перейдите по списку элементов, каждый раз добавляя элемент к дереву. Если элемент уже находится в дереве, просто увеличивайте счетчик в node. (или если вы хотите, чтобы фактические элементы вы могли сохранить список в каждом node)
Дерево будет содержать не более k.
в конце, перейдите дерево по-некорректному и добавьте элементы в правильном порядке (при добавлении количества, которое находится в счетчике node).
Сложность: O (nlogk)
Да, вы можете использовать массив размером k. (Без сравнений)
Каждая ячейка я будет содержать список.
перейдите к исходному массиву, поместите каждый элемент в список правой ячейки.
Перейдите по второму массиву и вытащите их, верните их в правильном порядке.
О (п)