Рассмотрим следующую проблему:
Входные данные : списки целых чисел
Цель : определить, существует ли целое число в обоих списках.
Предположим, что оба списка имеют размер . Существует ли детерминистический алгоритм с линейным временем для этой задачи? Другими словами, можете ли вы решить эту проблему за времени детерминистически, без использования случайности?
К сожалению, вы не можете предполагать, что элементы списка все маленькие.
Я могу видеть, как решить это за ожидаемое время, используя рандомизированный алгоритм: случайным образом выбрать 2-универсальную хеш-функцию , сохранить элементы в хеш-таблицу (используя в качестве хеш-функции), а затем посмотреть вверх каждый элемент чтобы увидеть, если он находится в хеш-таблице. Ожидаемое время работы будет . Тем не менее, я не вижу, как найти детерминированный алгоритм с времени выполнения. Если вы попытаетесь дерандомизировать это и исправить одну конкретную хеш-функцию, будет существовать входная информация для наихудшего случая, которая заставит эту процедуру выполняться ввремя. Лучший детерминированный алгоритм, который я могу найти, включает в себя сортировку значений, но это не будет линейным временем. Можем ли мы достичь линейного времени работы?
Кроме того, я могу увидеть, как решить это за линейное время, если предположить, что все элементы списка являются целыми числами в диапазоне (в основном, делать подсчет сортировки) - но меня интересует, что происходит в общем случай, когда мы не можем предположить, что.
Если ответ зависит от модели вычислений, модель ОЗУ приходит на ум, но мне будут интересны результаты для любой разумной модели вычислений. Я знаю о нижних границах для алгоритмов дерева решений для уникальности элементов , но это не является окончательным, поскольку иногда мы можем найти алгоритмы с линейным временем, даже когда есть связан в модели дерева решений.
Ответы:
Вы можете решить проблему за линейное время, если у вас достаточно памяти, чтобы иметь бит для каждого возможного значения в X и Y. Это не накладывает никаких ограничений на порядок X и Y.
источник
Поскольку вы говорите, что два списка содержат целые числа, я думаю, что мы можем запустить радикальную сортировку по двум спискам, а затем выполнить линейный поиск, сравнивая два списка для эквивалентных элементов.
источник
Почему бы не вставить целые числа каждого списка в простой побитовой трие? Будет ли это не быть оптимальным в том смысле , что оно является , где ¯ м среднего размера битого целых чисел; в частности, я не вижу, как вы можете добиться большего успеха, поскольку простое * чтение * двух списков заняло бы такое количество времени.O(n⋅m¯¯¯¯¯) m¯¯¯¯¯
источник
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 ofO(nlogn) .
источник