Эффективно найти статистику заказов префиксов несортированных списков?

A - это массив целых чисел от 1 до n в случайном порядке.

Мне нужен произвольный доступ к i -му наибольшему элементу из первых элементов j, по крайней мере, в течение времени журнала.

То, что я до сих пор придумал, это n x n matrix M, где элемент в позиции (i, j) является i th самым большим из первых j. Это дает мне постоянный произвольный доступ, но требует хранения n^2.

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

Может ли кто-нибудь предложить способ сжимать M до места n log(n) или лучше, с log(n) или лучшим временем произвольного доступа?

Ответ 1

Я считаю, что вы можете выполнить доступ в O (log (N)) времени, учитывая время предварительной обработки O (N log (N)) и O (N log (N)) дополнительного пространства. Вот как.

Вы можете увеличить красно-черное дерево, чтобы поддержать операцию select(i), которая извлекает элемент в ранге i в O (log (N)) времени. Например, см. Этот PDF или соответствующую главу "Введение в алгоритмы".

Вы можете реализовать красно-черное дерево (даже одно дополненное для поддержки select(i)) функциональным образом, так что операция insert возвращает новое дерево, которое разделяет все узлы O (log (N)) со старым дерево. См. Например, Чисто функциональные структуры данных Криса Окасаки.

Мы построим массив T чисто функционально дополненных красно-черных деревьев, так что дерево T[j] хранит индексы 0 ... j-1 из первых j элементов A, отсортированных по наименьшему.

Базовый регистр: в T[0] создать увеличенное красно-черное дерево с одним node, чьи данные - это число 0, которое является индексом 0-го по величине элемента в первых 1 элементах вашего массива A.

Индуктивный шаг: для каждого j от 1 до N-1 в T[j] создайте увеличенное красно-черное дерево, чисто функционально вставив новый node с индексом j в дерево T[j-1]. Это создает не более O (log (j)) новых узлов; остальные узлы разделяются с помощью T[j-1]. Это занимает время O (log (j)).

Общее время построения массива T равно O (N log (N)), а общее используемое пространство также O (N log (N)).

После создания T[j-1] вы можете получить доступ к i th наибольшему элементу из первых j элементов A, выполнив T[j-1].select(i). Это занимает время O (log (j)). Обратите внимание, что вы можете создать T[j-1] лениво в первый раз, когда это необходимо. Если A очень велико, а j всегда относительно мало, это сэкономит много времени и пространства.

Ответ 2

Если я не понимаю, вы просто находите k-й порядок статистики массива, который является префиксом другого массива.

Это можно сделать с помощью алгоритма, который, как мне кажется, называется "quickselect" или что-то в этом роде. В принципе, это похоже на quicksort:

Возьмите случайный стержень
Обменивайте элементы массива, чтобы все меньшие были с одной стороны.
Вы знаете, что это p + 1-й наибольший элемент, где p - количество меньших элементов массива.
Если p + 1 = k, то это решение! Если p + 1 > k, повторите на "меньшем" подмассиве. Если p + 1 < k, повторите на более крупном "подмассиве".

Здесь (намного) лучшее описание здесь под заголовками Quickselect и Quicker Select, а также просто в Интернете, если вы ищете k -го порядка для быстрой сортировки.

Хотя наихудшим временем для этого алгоритма является O (n2), как quicksort, его ожидаемый случай намного лучше (также как quicksort), если вы правильно выбираете свои случайные опорные точки. Я думаю, что сложность пространства будет только O (n); вы можете просто сделать одну копию своего префикса, чтобы подделать заказ.