Jump to content

Проблема различимости элементов

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

Это хорошо изученная проблема во многих различных моделях вычислений. Проблему можно решить, отсортировав список и проверив, есть ли последовательные равные элементы; его также можно решить за линейное ожидаемое время с помощью рандомизированного алгоритма , который вставляет каждый элемент в хеш-таблицу и сравнивает только те элементы, которые помещены в одну и ту же ячейку хеш-таблицы. [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]

См. также

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