Детерминированный алгоритм линейного времени, чтобы проверить, является ли один массив отсортированной версией другого

Рассмотрим следующую проблему:

Вход: два массива $A$ и $B$ длиной $n$ , где $B$ в отсортированном порядке.

Запрос: делать и B содержат одни и те же элементы (с учетом кратности)?$A$$B$

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

Вы не указали свою модель вычислений, поэтому я приму модель сравнения.

Рассмотрим частный случай, когда массив берется из списка { 1 , 2 } × { 3 , 4 } × ⋯ × { 2 n - 1 , 2 n } . Словом, i- й элемент равен 2 i - 1 или 2 i .$B$

$$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$$ $i$$2i-1$$2i$

Я утверждаю , что если алгоритм делает вывод , что и Б содержат те же самые элементы, что алгоритм сравнил каждый элемент B с его аналогом в A . Действительно, предположим , что алгоритм делает вывод , что и B содержат одни и те же элементы, но никогда не сравнивает первый элемент B его аналога в A . Если мы переключим первый элемент, алгоритм будет действовать точно так же, даже если ответ будет другим. Это показывает , что алгоритм должен сравнить первый элемент (и любой другой элемент) к его аналогу в A .$A$$B$$B$$A$$A$$B$$B$$A$$A$

Это означает , что если и Б содержат те же самые элементы, то после проверки этого алгоритм знает отсортированный порядок А . Следовательно, он должен иметь хотя бы n ! разные листья, и поэтому требуется время Ω ( n log n ) .$A$$B$$A$$n!$$\Omega(n\log n)$

$O(\log n)$$O(1)$$n^{O(1)}$

$a_1,\ldots,a_n$$b_1,\ldots,b_n$$1/n$

$$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$$ $p$$x_0$ $$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$$ $\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$$a_i,b_i$$n^{O(1)}$$2^n n^{O(n)} = n^{O(n)}$$O(n)$$\Omega(n)$$n^2$$p$$n^2$$p$$1-1/n$x 0 p 1 - n / p ≥ 1 - 1 / n n $$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$$ $x_0$$p$$1-n/p \geq 1-1/n$$n$$n$

В заключение, если мы выберем случайное число размером примерно среди набора из по крайней мере различных простых чисел и случайное число по модулю , то, когда массивы не содержат одинаковые элементы, наш тест не пройден с вероятностью . Выполнение теста занимает время поскольку соответствует постоянному числу машинных слов.n 2 n 2 x 0 p 1 - O ( 1 / n ) O ( n ) $p$$n^2$$n^2$$x_0$$p$$1-O(1/n)$$O(n)$$p$

Используя тестирование простоты за полиномиальное время, и поскольку плотность простых чисел размером примерно равна , мы можем выбрать случайное простое число во времени . Выбор случайного по модулю может быть реализован различными способами, и это делается проще, поскольку в нашем случае нам не нужен полностью равномерный случайный случай .$n^2$$\Omega(1/\log n)$$p$$(\log n)^{O(1)}$$x_0$$p$$x_0$

В заключение, наш алгоритм выполняется за время , всегда выдает YES, если массивы содержат одинаковые элементы, и выдает NO с вероятностью если массивы не содержат одинаковые элементы. Мы можем улучшить вероятность ошибки на для любой константы .$O(n)$$1-O(1/n)$$1-O(1/n^C)$$C$

я предложу другой алгоритм (или хотя бы схему такого алгоритма)

Схема предполагает, что значения (предполагаемые « целые числа ») находятся в (узком?) Диапазоне между$[min,max]$

1. В времени сканирования двух массивов, мы можем найти и значения для обоих и их кратности, если они отличаются, массивы не являются перестановками друг друга$O(n)$minmax

2. Вычтите minиз всех значений из обоих массивов (здесь тот факт, что один массив уже находится в отсортированном порядке, не учитывается, возможно, это можно улучшить)

3. Предположим, что значения в массивах представляют массы, и мы применяем ускорение / скорость к каждому из величин (это может быть улучшено до величины в некоторых случаях)с > $1$$c > 1$

4. перемещайте массы, пока они не достигнут максимального значения max-min, это имеет сложность . Это позволяет найти как одинаковые значения, так и их кратность, если они различаются, массивы не являются перестановками друг друга. Еще решить, что массивы являются перестановками друг друга.$O((max-min)n)$

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

Приведенная выше схема алгоритма представляет собой разновидность алгоритма линейной сортировки по времени с использованием « движущихся масс ». Физическая интуиция, лежащая в основе алгоритма сортировки " движущихся масс ", такова:

Предположим, что ценность каждого элемента фактически представляет его массовую величину, и представьте, что вы располагаете все элементы в линию и применяете одну и ту же силу ускорения.

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

Этот алгоритм является линейно-временным и детерминированным , но есть оговорка в том, что величина начальной ускоряющей силы и расстояния для перемещения (или времени ожидания) связана с распределением значений (то есть « масс », фактор выше). Можно также попытаться дискретизировать пространство для перемещения элементов в сетку и получить постоянный коэффициент скорости алгоритма (и использовать процедуру быстрой сортировки для сортировки различных элементов в одной и той же ячейке ).$max-min$

В этом отношении вышеприведенный алгоритм аналогичен алгоритмам сортировки на основе чисел (например, радикальная сортировка , счетная сортировка )

Можно подумать, что этот алгоритм может ничего не значить, но он показывает, по крайней мере, одну вещь. То, что «на фундаментальном уровне» сортировка произвольных чисел на физическом уровне является линейной операцией с числом элементов.