Проблема отличимости элементов - Element distinctness problem

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

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

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

Сложность дерева решений

Известно, что для списков чисел проблема временная сложность является Θ (п бревно п), т.е. как верхняя, так и нижняя оценки ее временной сложности имеют порядок линейная функция в алгебраическое дерево решений модель вычисления,[2] модель вычислений, в которой элементы не могут использоваться для индексации памяти компьютера (как в решении хеш-таблицы), но могут быть доступны только путем вычисления и сравнения простых алгебраических функций их значений. Другими словами, асимптотически оптимальный для этой модели известен алгоритм линейной временной сложности. Модель дерева алгебраических вычислений в основном означает, что допустимые алгоритмы - это только те, которые могут выполнять полиномиальные операции ограниченной степени над входными данными и сравнения результатов этих вычислений.

Такая же оценка снизу была позже доказана для рандомизированный алгебраическое дерево решений модель.[3][4]

Квантовая сложность

Также известно, что квантовые алгоритмы может решить эту проблему быстрее, в запросы. Оптимальный алгоритм: Андрис Амбайнис.[5] Яоюнь Ши впервые доказал жесткую нижнюю границу, когда размер диапазона достаточно велик.[6] Амбаинис[7] и Кутин[8] независимо (и с помощью различных доказательств) расширил свою работу, чтобы получить нижнюю оценку для всех функций.

Обобщение: поиск повторяющихся элементов

Элементы, встречающиеся более чем п/k раз в мультимножестве размера n можно найти за время O (п бревно k). Проблема отличимости элементов - это частный случай k=п. Этот алгоритм оптимален при модель дерева решений вычисления.[9]

Алгоритм является обобщением алгоритма для частного случая k= 2 ( Алгоритм большинства голосов Бойера – Мура ), у которого была довольно запутанная история публикации.[10]

Вышеупомянутые алгоритмы полагаются только на проверку идентичности элементов. Если сортировка разрешена, заранее известно статистика заказов алгоритмы поиска могут быть использованы. Например, для k= 2, а медиана может быть найден первым в линейное время, и тогда можно легко проверить, есть ли больше, чем п/ 2 срединных элемента. Однако указанные выше алгоритмы требуют меньшего количества сравнений, чем алгоритмы статистики порядка.[10]

Смотрите также

Рекомендации

  1. ^ Gil, J .; Meyer auf der Heide, F .; Вигдерсон, А. (1990), «Не все ключи можно хешировать за постоянное время», Proc. 22-й симпозиум ACM по теории вычислений, стр. 244–253, Дои:10.1145/100216.100247.
  2. ^ Бен-Ор, Майкл (1983), "Нижние оценки для алгебраических вычислительных деревьев", Proc. 15-й симпозиум ACM по теории вычислений, стр. 80–86, Дои:10.1145/800061.808735.
  3. ^ Григорьев Дима; Карпинский, Марек; Хайде, Фридхельм Мейер; Смоленский, Роман (1996), "Нижняя оценка для рандомизированных алгебраических деревьев решений", Вычислительная сложность, 6 (4): 357, Дои:10.1007 / BF01270387.
  4. ^ Григорьев Дима (1999), "Нижние границы сложности для рандомизированных вычислительных деревьев над нулевыми характеристическими полями", Вычислительная сложность, 8 (4): 316–329, Дои:10.1007 / с000370050002.
  5. ^ Амбайнис, Андрис (2007), «Алгоритм квантового блуждания для различимости элементов», SIAM Журнал по вычислениям, 37 (1): 210–239, arXiv:Quant-ph / 0311001, Дои:10.1137 / S0097539705447311
  6. ^ Ши, Ю. (2002). Квантовые нижние оценки проблемы столкновения и различимости элементов. Материалы 43-го Симпозиум по основам информатики. С. 513–519. arXiv:Quant-ph / 0112086. Дои:10.1109 / SFCS.2002.1181975.
  7. ^ Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различимость элементов с малым радиусом действия». Теория вычислений. 1 (1): 37–46. Дои:10.4086 / toc.2005.v001a003.
  8. ^ Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновения с малым радиусом действия». Теория вычислений. 1 (1): 29–36. Дои:10.4086 / toc.2005.v001a002.
  9. ^ Misra, J .; Грис, Д. (1982), «Поиск повторяющихся элементов», Наука компьютерного программирования, 2 (2): 143–152, Дои:10.1016/0167-6423(82)90012-0, HDL:1813/6345.
  10. ^ а б Бойер, Р.С.; Мур, Дж. С. (1991), «MJRTY - алгоритм быстрого голосования большинством», в Бойе, Р. С. (ред.), Автоматизированное рассуждение: очерки в честь Вуди Бледсо, Automated Reasoning Series, Дордрехт, Нидерланды: Kluwer Academic Publishers, стр. 105–117..