Проблема различимости элементов
В теории сложности вычислений или проблема различимости элементов проблема уникальности элементов — это проблема определения того, все ли элементы списка различны.
Это хорошо изученная проблема во многих различных моделях вычислений. Проблему можно решить, отсортировав список и проверив, есть ли последовательные равные элементы; его также можно решить за линейное ожидаемое время с помощью рандомизированного алгоритма , который вставляет каждый элемент в хеш-таблицу и сравнивает только те элементы, которые помещены в одну и ту же ячейку хеш-таблицы. [1]
Ряд нижних оценок вычислительной сложности доказывается путем сведения проблемы различимости элементов к рассматриваемой задаче, т. е. путем демонстрации того, что решение проблемы уникальности элемента может быть быстро найдено после решения рассматриваемой задачи.
Сложность дерева решений
[ редактировать ]Число сравнений, необходимое для решения проблемы размера , в модели вычислений на основе сравнения, такой как дерево решений или алгебраическое дерево решений , . Здесь, использует большую тэта-нотацию , что означает, что проблема может быть решена за счет числа сравнений, пропорционального ( линейная функция ) и что все решения требуют такого количества сравнений. [2] В этих моделях вычислений входные числа не могут использоваться для индексации памяти компьютера (как в решении хеш-таблицы), но доступны только путем вычисления и сравнения простых алгебраических функций их значений. Для этих моделей алгоритм, основанный на сортировке сравнения, решает проблему с точностью до постоянного коэффициента наилучшего возможного числа сравнений. Та же нижняя граница применима и к ожидаемому количеству сравнений в модели рандомизированного алгебраического дерева решений . [3] [4]
Реальная сложность оперативной памяти
[ редактировать ]Если элементами в задаче являются действительные числа , нижняя граница дерева решений распространяется на реальную модель машины с произвольным доступом с набором команд, который включает в себя сложение, вычитание и умножение действительных чисел, а также сравнение и деление или получение остатка ( "пол"). [5] Отсюда следует, что сложность задачи в этой модели также . Эта модель RAM охватывает больше алгоритмов, чем модель алгебраического дерева решений, поскольку она включает алгоритмы, использующие индексацию в таблицах. Однако в этой модели учитываются все шаги программы, а не только решения.
Сложность машины Тьюринга
[ редактировать ]Одноленточная детерминированная машина Тьюринга может решить задачу для n элементов по m ≥ log n бит каждый за время O ( n 2 м ( м +2–log n )) , в то время как на недетерминированной машине временная сложность равна O ( nm ( n + log m )) . [6]
Квантовая сложность
[ редактировать ]Квантовые алгоритмы могут решить эту проблему быстрее, в запросы. Оптимальный алгоритм — Андрис Амбайнис . [7] Яоюнь Ши впервые доказал точную нижнюю границу, когда размер диапазона достаточно велик. [8] Амбайнис [9] и Кутин [10] независимо (и посредством различных доказательств) расширил свою работу, чтобы получить нижнюю оценку для всех функций.
Обобщение: поиск повторяющихся элементов
[ редактировать ]Элементы, встречающиеся более чем раз в мультинаборе размера может быть найден с помощью алгоритма, основанного на сравнении, алгоритма сильных нападающих Мисры-Гриса , за время . Проблема различимости элементов является частным случаем этой проблемы, когда . Это время оптимально в рамках модели вычислений в виде дерева решений . [11]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Гил, Дж.; Мейер ауф дер Хайде, Ф.; Вигдерсон, А. (1990), «Не все ключи можно хешировать за постоянное время», Proc. 22-й симпозиум ACM по теории вычислений , стр. 244–253, doi : 10.1145/100216.100247 , S2CID 11943779 .
- ^ Бен-Ор, Майкл (1983), «Нижние оценки для деревьев алгебраических вычислений», Proc. 15-й симпозиум ACM по теории вычислений , стр. 80–86, doi : 10.1145/800061.808735 .
- ^ Григорьев Дима ; Карпински, Марек ; Хайде, Фридхельм Мейер; Смоленский, Роман (1996), «Нижняя оценка для рандомизированных алгебраических деревьев решений», Computational Complexity , 6 (4):357, doi : 10.1007/BF01270387 , S2CID 1462184 .
- ^ Григорьев, Дима (1999), «Нижние границы сложности для рандомизированных деревьев вычислений над полями с нулевой характеристикой», Computational Complexity , 8 (4): 316–329, doi : 10.1007/s000370050002 , S2CID 10641238 .
- ^ Бен-Амрам, Амир М.; Галил, Цви (2001), «Топологические нижние границы алгебраических машин произвольного доступа», SIAM Journal on Computing , 31 (3): 722–761, doi : 10.1137/S0097539797329397 .
- ^ Бен-Амрам, Амир М.; Беркман, Омер; Петерсен, Хольгер (2003), «Различность элементов на одноленточных машинах Тьюринга: комплексное решение», Acta Informatica , 40 (2): 81–94, doi : 10.1007/s00236-003-0125-8 , S2CID 24821585
- ^ Амбайнис, Андрис (2007), «Алгоритм квантового обхода для определения различимости элементов», SIAM Journal on Computing , 37 (1): 210–239, arXiv : quant-ph/0311001 , doi : 10.1137/S0097539705447311
- ^ Ши, Ю. (2002). Квантовые нижние оценки для проблем столкновений и различий элементов . Материалы 43-го симпозиума по основам информатики . стр. 513–519. arXiv : Quant-ph/0112086 . дои : 10.1109/SFCS.2002.1181975 .
- ^ Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном» . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .
- ^ Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .
- ^ Мисра, Дж.; Грис, Д. (1982), «Нахождение повторяющихся элементов», Science of Computer Programming , 2 (2): 143–152, doi : 10.1016/0167-6423(82)90012-0 , hdl : 1813/6345 .