Память и эффективная по времени сортировка всех вращений длинного массива

Question

Я ищу память и эффективное по времени решение указанной ниже проблемы. Легко думать о базовом c алгоритме, который использует O (n ² ) памяти и O (n ² log n) времени (?), И я хотел бы знать, если существует алгоритм, который значительно более эффективен в отношении памяти и времени (для определенных структур ввода).

Input : Массив a длины n, заполненный неотрицательными целыми числами. Каждое целое число в массиве имеет величину, меньшую или равную b. Меня интересуют настройки, где n велико (десятки миллионов), а b относительно мало по сравнению с n (сотнями). Можно предположить, что число вхождений любого конкретного целого числа в a ограничено сверху m, где m порядка n / b.

Рассмотрим множество всех вращений массива a, т. Е. если a = (a ₁ , a ₂ , ..., a _n ), то его повороты составляют (a ₁ , a ₂ , ..., a _n ), (a ₂ , a ₃ , ..., a _n , a ₁ ), (a ₃ , a ₄ , ..., a _n , a ₁ , a ₂ ), ..., (a _n , a ₁ , a ₂ , .. ., _n-1 ). Пусть r ₁ , r ₂ , ..., r _n обозначают лексикографически отсортированный (увеличивающийся) порядок вращения массива a (используя 0 <1 <2 <... <b). </p>

Выход : Два массива первый и последний , в которых хранятся первый и последний элементы r ₁ , r ₂ , ..., r _n в соответствии с отсортированным порядком.

Базовый c алгоритм (без использования памяти или времени): составьте все повороты a и сохраните их в матрице A (в которой используется память O (n ² )). Определите процедуру сортировки (которая использует стандартную технику сортировки) для сортировки А. Извлеките первый и последний столбцы отсортированной матрицы. Предположительно, лучшая временная сложность этапа сортировки составляет O (n ² log n), т. Е. O (n log n) для алгоритма сортировки, умноженного на O (n) для каждого парного сравнения.

Второй алгоритм : мы можем пройти по массиву и сохранить в нем позиции, которые начинаются с любого целого числа i, меньшего или равного b (это время O (n) и O (нм) операция памяти). Затем мы можем сгенерировать все вращения, начиная с определенного целого числа i, и отсортировать эту матрицу вращений в соответствии с алгоритмом basi c (хранение этой матрицы использует память O (nm), а сортировка предположительно занимает время O (mn log m)). Выходные данные легко сконструировать, повторяя процесс для каждого целого числа i от 0 до b.

Существует ли подход, более эффективный для памяти, в котором используется специализированная стратегия сортировки? Я надеюсь, что для хранения выходных данных требуется только O (n) памяти.

Answer 1

Рассчитать массив суффиксов для данного массива в O (nlogn). Обратите внимание, что связанная реализация сортирует циклические c сдвиги (там используется специальный символ для суффиксов - он вам не нужен) - именно то, что вам нужно (но "сортирует" без физической сортировки)

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

P[0] содержит позицию наименьшего циклического c смещения, поэтому A[P[0]] и A[P[0]-1] - первая пара, P[1] - позиция следующего наименьшего сдвига и т. Д.

Answer 2

Давайте построим лучший алгоритм для поиска первого поворота. Построение последнего в лексикографическом порядке - это та же проблема, но сортировка в обратном порядке. Все, что нам нужно отследить, это то, каков минимальный поворот и какие позиции мы могли бы быть в настоящее время. Вот для этой идеи Python.

def min_rotation (elements):
    rotation = []
    positions = [i for i in range(len(elements))]
    while len(rotation) < len(elements):
        min_element = elements[positions[0]]
        new_positions = []
        for i in range(len(positions)):
            # Get the position and start rotating.
            position = positions[i]
            if elements[position] < min_element:
                min_element = elements[position]
            elif min_element <elements[position]:
                continue
            new_position = (position + 1) % len(elements)
            new_positions.append(new_position)
        positions = new_positions
        rotation.append(min_element)
    return rotation

В худшем случае O(n) память и O(n*n) время выполнения. Вы попадете в константный массив.

Ожидаемый случай будет O(n) время выполнения, потому что число positions быстро перемещается к 1.