Подборка рутины с обманщиками?

Question

Недавно я написал программу после анализа алгоритма k-го наименьшего элемента, сначала без случая дубликатов.

Теперь, однако, я хотел бы проанализировать ожидаемую асимптотическую среду выполнения для нахождения, скажем, медианы массива, когда точно j дубликаты. Я не модифицировал свой код для такого, и поэтому производительность немного замедляется из-за j дубликаты.

Я не уверен, как начать? Кто-нибудь может указать мне на такое возвращение отношения?

Я вывел следующее, где n - размер входного массива

T(n) <= 1/2*T(3/4*n) + 1/2*T(n)

но совершенно неясно, как поступить с дублирующимися ключами.

Спасибо

Answer 1

Рандомизированное решение, как показано здесь

 T(n) <= T(3/4*n) + n-1  =>  T(n) <= 4n

Сложность алгоритма может зависеть от j но не ожидайте, что оно будет чудесным образом меньше линейного времени. Зачем? возьмите случайный массив размером n/2, полностью продублируйте его и запустите идеальный алгоритм для задачи с дубликатами. Вы будете иметь

T(n) <= 4(n/2) => T(n) <= 2n

когда каждый элемент дублируется дважды (точно n/2 дубликаты)