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

9

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

Входные данные : списки X,Y целых чисел

Цель : определить, существует ли целое число в обоих списках.x

Предположим, что оба списка имеют размер . Существует ли детерминистический алгоритм с линейным временем для этой задачи? Другими словами, можете ли вы решить эту проблему за времени детерминистически, без использования случайности?X,YnO(n)

К сожалению, вы не можете предполагать, что элементы списка все маленькие.


Я могу видеть, как решить это за ожидаемое время, используя рандомизированный алгоритм: случайным образом выбрать 2-универсальную хеш-функцию , сохранить элементы в хеш-таблицу (используя в качестве хеш-функции), а затем посмотреть вверх каждый элемент чтобы увидеть, если он находится в хеш-таблице. Ожидаемое время работы будет . Тем не менее, я не вижу, как найти детерминированный алгоритм с времени выполнения. Если вы попытаетесь дерандомизировать это и исправить одну конкретную хеш-функцию, будет существовать входная информация для наихудшего случая, которая заставит эту процедуру выполняться вO(n)hXhYO(n)O(n)Θ(n2)время. Лучший детерминированный алгоритм, который я могу найти, включает в себя сортировку значений, но это не будет линейным временем. Можем ли мы достичь линейного времени работы?

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

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

DW
источник
Хеш-таблицы O (n log n), так как вам нужно обрабатывать коллизии.
Торбьерн Равн Андерсен
1
@ ThorbjørnRavnAndersen, я не вижу, откуда ты это взял. Использование 2-х универсальных хеш-функций и хеш-таблицы подходящего размера гарантирует, что число коллизий хешей минимально (с высокой вероятностью), поэтому я считаю, что время выполнения достижимо. Я не уверен, откуда ты взял O ( n lg n ) ; если вы не делаете что-то особенное (например, используете 2-универсальное хеширование), худший случай - O ( n 2 ) из-за коллизий. O(n)O(nlgn)O(n2)
DW
Дьявол кроется в деталях, здесь «хэш-таблица подходящего размера». Это может оказаться довольно большим, если вы не хотите столкновения. Типичный n-log-n - это (если я правильно помню) для обработки коллизий хеш-функций со списком.
Турбьёрн Равн Андерсен
1
@ ThorbjørnRavnAndersen Ожидаемое количество ключей, сопоставляемых одному и тому же адресу, является постоянным (для таблиц, которые не перегружены), поэтому тип разрешения конфликтов не имеет значения. Смотрите также здесь . соответствует худшему случаю, если вы используете (внешние) сбалансированные BST вместо списков. O(nlogn)
Рафаэль

Ответы:

1

Вы можете решить проблему за линейное время, если у вас достаточно памяти, чтобы иметь бит для каждого возможного значения в X и Y. Это не накладывает никаких ограничений на порядок X и Y.

  1. Первоначально все биты не установлены.
  2. Итерируйте по X, устанавливая соответствующий бит.
  3. Выполните итерацию по Y, проверяя, был ли установлен соответствующий бит выше.
Турбьерн Равн Андерсен
источник
2
К сожалению, вы не можете предполагать, что все целые числа маленькие (вы не можете предполагать, что они достаточно малы, чтобы этот алгоритм работал). В общем случае время выполнения этого алгоритма будет экспоненциальным по длине в битах элементов списка. Однако, спасибо!
DW
Давайте назовем его «битовый массив подходящего размера». Также линейный по длине в битах эквивалентен log-n. Вы серьезно относитесь к получению производительности log-n без каких-либо ограничений или предварительных условий для входных данных?
Торбьерн Равн Андерсен
2
@ ThorbjørnRavnAndersen Пространство экспоненциально по длине в битах (необходимо отобразить все возможные значения), а время является линейным по общему размеру списка (вам необходимо просмотреть все значения в обоих списках). Ничто не является линейным по длине в битах.
wchargin
0

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

Anirudh
источник
4
Это работает, только если есть ограничение на величину чисел.
Люк Мэтисон
но я думал, что высокая величина будет проблемой только для подсчета сортировки, а для сортировки по основанию мы можем выбрать достаточно высокое основание для решения этой проблемы ... пожалуйста, дайте мне знать, чего мне здесь не хватает
anirudh
Что если одно из чисел 2 ^ (2 ^ 128)?
miniBill
@anirudh, но тогда у вас будет другой алгоритм для разных входных размеров - вам нужен больший алфавит при каждом увеличении радиуса, вы просто экспортируете сложность увеличения величины в увеличение размера алфавита. Конечно, это возможно только в теории, я не думаю, что много аппаратного обеспечения позволяет вам изменять, в какой базе он представляет числа (мы можем притворяться на концах ввода и вывода, но это сводится к (в основном) двоичному ).
Люк Мэтисон
0

Почему бы не вставить целые числа каждого списка в простой побитовой трие? Будет ли это не быть оптимальным в том смысле , что оно является , где ¯ м среднего размера битого целых чисел; в частности, я не вижу, как вы можете добиться большего успеха, поскольку простое * чтение * двух списков заняло бы такое количество времени.O(nm¯)m¯

Реал Слав
источник
O(n)O(n\overbarm)
wmм¯, что приводит к времени выполнения О(N), or am I mistaken?
Realz Slaw
hmm maybe considering w a constant is a mistake.
Realz Slaw
(w is not considered constant, but dependant on n: you can have it any constant multiple m of what is necessary to represent n (wide enough to represent nm), just not arbitrarily large.)
greybeard
-1

It is similar to the Elemet Uniqueness problem, where you have a set of n numbers and you want to determine whether all of the elements are distinct. The problem has an algebraic computation tree lower bound of O(nlogn).

Omer Gold
источник
1
The question is quite explicit about linear deterministic time, not log-linear. Also to determine if (not on what value) set has only unique elements you can do faster than loglinear.
Evil
1
Do you mean Ω(nlogn)? If so, that might suggest that the problem in the question can't be solved in linear time. But just saying that a related problem can be solved in log-linear time doesn't really answer the question. (cc @EvilJS)
David Richerby
1
Thanks for your note. I wonder if you missed the last sentence of the question. I'll repeat it here: "I'm aware of Ω(nlogn) lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a Ω(nlogn) bound in the decision-tree model." In other words, this answer doesn't answer the question; it merely repeats something that I already said in the question I was aware of, but which doesn't resolve the question.
D.W.
It can be done in O(nloglogn) time which is better than given O(nlogn), so I am sure this was not Ω(nlogn), but this does not solve the D.W. question. So just comment here.
Evil