Сортировка массива из n элементов с O (logn) различными элементами за O (nloglogn) наихудшее время

Question

Проблема в том, что в самом заголовке. То есть дать алгоритм, который сортирует массив из n элементов с O (logn) различными элементами за O (nloglogn) время наихудшего случая. Есть идеи?

Далее, как вы обычно обрабатываете массивы с несколькими не различимыми элементами?

Answer 1

O (log (log ( n ))) достаточно времени для выполнения примитивной операции в дереве поиска с элементами O (log ( n )).

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

Пройдите по элементам ввода один за другим.Для каждого элемента попробуйте вставить его в дерево (что занимает время O (журнал журнала n )).Если вы обнаружите, что уже видели равный элемент, просто вставьте его во вспомогательный список в уже существующем узле.

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

Answer 2

Некоторые подробности об использовании дерева:

Вы должны иметь возможность использовать красное черное дерево (или другой тип алгоритма сортировки на основе дерева), используя узлы, которые содержат как значение, так и счетчик: возможно, кортеж(n, count).

Когда вы вставляете новое значение, вы либо создаете новый узел, либо увеличиваете счетчик узла добавляемым значением (если узел с этим значением уже существует).Если вы просто увеличите счетчик, вам потребуется O (logH), где H - высота дерева (чтобы найти узел), если вам нужно его создать, потребуется также O (logH), чтобы создать и расположить узел (константы больше, но они все равно O (logH).

Это гарантирует, что дерево будет иметь не более O (logn) значений (поскольку у вас есть log n различных значений). Это означает, что вставкапримет O (loglogn), и у вас есть n вставок, поэтому O (nloglogn).

Answer 3

Простое решение для журнала (N) было бы:

найти отдельные элементы, используя сбалансированное дерево (log (n) пространство, n + log (n) == n время)
, чем вы можете использоватьэто дерево всегда выбирает правильный поворот для быстрой сортировки.

Интересно, есть ли решение для пространства журнала (log (N)).