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

19

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

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

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

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

Альберт Хендрикс
источник
1
FWIW вероятностный подход хэширование с независимой от порядка хэш-функцией. Картер и Вегман написали одну из оригинальных статей по этому вопросу ( sciencedirect.com/science/article/pii/0022000081900337 ), но я не видел в цитатах этой статьи ничего, что предлагало бы детерминистический алгоритм (пока).
KWillets
1
Цитируемое вами утверждение касается модели машины Тьюринга, которая представляет только теоретический интерес. Алгоритмы обычно анализируются относительно модели RAM.
Юваль Фильмус
ах, тогда это модель, которую я ищу. Я поправил вопрос.
Альберт Хендрикс
Почему бы вам просто не суммировать элементы в массиве, а затем сравнить суммирование? Что касается вашего заголовка, он линейный и отвечает на вопрос «является ли один массив отсортированной версией другого? ». Я знаю, что это не модель машины Тьюринга, а практическое решение.
Атайенел
1
@AlbertHendriks Вы (скорее всего) не можете отсортировать массив в O(nlogn) на машине Тьюринга. Некоторые нижние границы для SAT (например, cs.cmu.edu/~ryanw/automated-lbs.pdf ) на самом деле относятся к ОЗУ, извините за мой вводящий в заблуждение предыдущий комментарий.
Юваль Фильмус

Ответы:

14

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

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

{1,2}×{3,4}××{2n1,2n}.
i2i12i

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

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

Юваль Фильмус
источник
P=Ω(nlogn)
@AlbertHendriks, это та же модель, которая использовалась, чтобы показать нижнюю границу для сортировки. Это означает, что единственная операция, которую вы можете выполнить, - это сравнение, тогда вы не можете сделать лучше. Я думаю, что это отвечает на ваш вопрос.
Каве
[Cntd] у нас нет более сильных границ даже для сортировки! и если вы можете сортировать быстрее, чем n lg n, то вы можете использовать это для решения проблемы быстрее, чем n lg n.
Каве
1
@ AlbertHendriks, вы знаете о линейных алгоритмах времени для сортировки целых чисел? Посмотрите это в CLRS. Ваш случай может быть одним из случаев, когда мы можем сортировать по линейному времени.
Каве
6
O(nloglogn)O(nloglogn)
10

O(logn)O(1)nO(1)

a1,,anb1,,bn1/n

i=1n(xai)=i=1n(xbi).
px0
i=1n(x0ai)i=1n(x0bi)(modp).
i=1n(xai)i=1n(xbi)ai,binO(1)2nnO(n)=nO(n)O(n)Ω(n)n2pn2p11/nx 0 p 1 - n / p 1 - 1 / n n n
i=1n(xai)i=1n(xbi)0(modp).
x0p1n/p11/nnn

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

Используя тестирование простоты за полиномиальное время, и поскольку плотность простых чисел размером примерно равна , мы можем выбрать случайное простое число во времени . Выбор случайного по модулю может быть реализован различными способами, и это делается проще, поскольку в нашем случае нам не нужен полностью равномерный случайный случай .n2Ω(1/logn)p(logn)O(1)x0px0

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

Юваль Фильмус
источник
1
Хотя этот алгоритм рандомизирован, он объясняет, как реализовать идеи в некоторых других ответах, чтобы они действительно работали. Он также имеет преимущество перед хэш-таблицей: он на месте.
Юваль Фильмус
Я думаю, что ОП не любит вероятностные алгоритмы, так как ему не нравился алгоритм ожидаемого линейного времени с использованием хеш-таблицы.
Каве
Каве ты прав. Но, конечно, это решение также интересно и должно быть сохранено, оно решает проблему для вероятностных алгоритмов. Кроме того, я думаю, что он использует модель, которую я ищу.
Альберт Хендрикс
1
Мне просто интересно, если обозначение O (1 / n) является правильным. Конечно, я знаю, что вы имеете в виду, но я думаю, что по определению big-O это эквивалентно O (1).
Альберт Хендрикс
2
Не за что. Это величина, ограниченная для достаточно большого . Это лучшая гарантия, чем . C/nnO(1)
Юваль Фильмус
-3

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

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

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

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

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

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

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

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

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

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

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

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

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

Никос М.
источник
С точки зрения сбора предметов в обратном порядке пройденного расстояния, не приведет ли это к сравнениям на уровне реализации, и в этот момент вам не нужно сортировать «расстояния»?
JustAnotherSoul