Анализ времени выполнения алгоритма Лас-Вегаса

Question

В массиве из n элементов, если n/2 являются повторяющимися элементами, а остальные являются различными, мы могли бы использовать алгоритм Лас-Вегаса для получения повторяющегося элемента в o (logn) времени.

Существует еще один вопрос, который гласит: каково минимальное количество повторений, необходимых для выполнения этого алгоритма o (logn), т.е. (n/k повторяющихся элементов, где k =?), И какова продолжительность выполнения, если повторяющийся элемент является корневым (п)?

В моем результате сказано, что это не o (logn), если повторяющийся элемент является корнем (n), но я не могу найти свободную привязку к этой проблеме, используя алгоритм Лас-Вегаса. Помощь будет оценена.

Answer 1

«Лас-Вегас» не является алгоритмом; это тип алгоритма. Очевидным алгоритмом является выборка пар элементов равномерно случайным образом до тех пор, пока они не совпадут. Когда массив имеет элемент, повторяемый n/2 раза, вероятность успеха для каждой пары равна ((n/2)/n) ((n/2-1)/(n-1)) = 1/4 - O (1/n), поэтому ожидаемое время работы равно 1/(1/4 - O (1/n)) = 4 + O (1/n) = O (1) выборкам.

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