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