Алгоритм «разделяй и властвуй» для сортировки списка, в котором каждый элемент является корневым (n) от своей отсортированной позиции

Question

Я застрял в вопросе, и мне просто нужна подсказка / указание в общем направлении (не спрашивая ответа)

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

То, что они имеют в виду под почти отсортированными, это то, что дано списком

x_1, x_2, .... x_n

, если отсортированный список представлен

y_1, y_2, ... y_n

и для каждого i, j <= n это свойство соблюдается: </p>

x_i == y_j && | i-j | <= root (n) </p>

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

Я также выяснил, что уравнение сложности рекурсии будет:

T (n) = root (n) * T (n / root (n)) + d * root (n)

, что с помощью master's theorem может быть доказано как O (n) время.

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

РЕДАКТИРОВАТЬ : Итак, предположительно, это был правильный ответ.

Наш алгоритм следующий: если n> 1, то мы рекурсивно сортируем каждую из двух (приблизительных) половин последовательности; теперь все элементы находятся в правильном положении, кроме, возможно, тех, которые находятся в √n положениях середины (вы понимаете, почему это так?); так что теперь мы делаем слияние элементов в этих позициях. Если мы позволим T (n) быть временем, используемым для сортировки элементов, то для n> 1 мы получим

T (n) ≤2T (⌈n = 2⌉) + c * √n

Поскольку √ (n) = n ^.5 и .5 <1 = log <sub>2 2, основная теорема для повторений «разделяй и властвуй» говорит нам, что T (n) ∈O (п). * * тысяча пятьдесят-одна

Я не уверен, согласен ли я, поскольку время сортировки обеих половинок будет равно O ( ⁿ & frasl; ₂ * log ( ⁿ & frasl; ₂ )), который работает как O (n * logn), а окончательное слияние будет O (√n * √n), что есть O (n), что дает нам всего O (n * logn + n) -> O (n * logn)

Answer 1

Я не верю, что сортировка на основе сравнения может сделать это в O(n).

Рассмотрим упрощенную проблему, когда отсортированный массив делится на √n сегментов, и элементы внутри каждоговедро перемешиваются.Условие, что каждый элемент должен находиться на расстоянии не более √n позиций от его конечной точки, удовлетворяется.

Чтобы решить эту проблему, вы должны отсортировать каждое ведро.Используя любую сортировку O(n*logn), вы получите √n * (√n * log√n).Это (1/2) * n * logn, которое по-прежнему O(n*logn).

Поскольку эту упрощенную проблему можно решить только в O(n*logn), я заключаю, что невозможно решить исходную проблему вO(n) с использованием сортировки на основе сравнения.

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

Answer 2

Такой алгоритм может быть использован для сортировки r списков из r элементов за O (r * r) времени, просто путем объединения списков (и декорирования элементов, если необходимо).Однако известно, что вы не можете добиться большего успеха, чем O (r * r * ln (r)) или O (n * ln (n)) для n = r * r.

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

Answer 3

Первая подсказка: T (n) = root (n) * T (n / root (n)) + d * root (n) неверно. Поскольку это рекурсивная функция, она не верна для T (root (n)).