Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Квантовая сложность [ править ]

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ Gil, J .; Meyer auf der Heide, F .; Вигдерсон, А. (1990), «Не все ключи можно хэшировать за постоянное время», Proc. Двадцать второй ACM симпозиум по теории вычислений ., Стр 244-253, DOI : 10,1145 / 100216,100247.
  2. ^ Бен-Ор, Майкл (1983), "Нижние оценки для алгебраических вычислительных деревьев", Proc. Пятнадцатый ACM симпозиум по теории вычислений ., Стр 80-86, DOI : 10,1145 / 800061,808735.
  3. ↑ Григорьев, Дима ; Карпинский, Марек ; Хайде, Фридхельм Мейер; Смоленский, Роман (1996), "Нижняя оценка для рандомизированных алгебраических деревьев решений", Вычислительная сложность , 6 (4): 357, doi : 10.1007 / BF01270387.
  4. ^ Григорьев, Дима (1999), "Сложность Нижние оценки для вычисления рандомизированных деревьев над нулевой характеристики полей", вычислительной сложности , 8 (4): 316-329, DOI : 10.1007 / s000370050002.
  5. ^ Амбаинис, Андрис (2007), «Алгоритм квантового обхода для различимости элементов», SIAM Journal on Computing , 37 (1): 210–239, arXiv : Quant-ph / 0311001 , doi : 10,1137 / S0097539705447311
  6. Перейти ↑ Shi, Y. (2002). Квантовые нижние оценки проблемы столкновения и различимости элементов . Материалы 43-го симпозиума по основам информатики . С. 513–519. arXiv : квант-ph / 0112086 . DOI : 10.1109 / SFCS.2002.1181975 .
  7. ^ Ambainis, A. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым радиусом действия» . Теория вычислений . 1 (1): 37–46. DOI : 10.4086 / toc.2005.v001a003 .
  8. ^ Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновений с малым радиусом действия» . Теория вычислений . 1 (1): 29–36. DOI : 10.4086 / toc.2005.v001a002 .
  9. ^ Misra, J .; Грис Д. (1982), "повторил Finding элементы", Наука компьютерного программирования , 2 (2): 143-152, DOI : 10,1016 / 0167-6423 (82) 90012-0 , ЛВП : 1813/6345.
  10. ^ a b Boyer, RS ; Мур, Дж. С. (1991), «MJRTY - алгоритм быстрого голосования большинством», в Boyer, RS (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe , Automated Reasoning Series, Dordrecht, Нидерланды: Kluwer Academic Publishers , стр. 105–117.