Нижняя граница для поиска наименьшего элемента KTH, используя аргументы противника

Question

Во многих текстах более низкая граница для поиска $ K $ th Latement Element получен с использованием аргументов с использованием медиан. Как я могу найти один, используя аргумент противника?

Википедия говорит, что алгоритм турнира работает в $ O (n+k log n) $ и $ n - k+ sum_ {j = n+2 -k}^{n} lceil { operatorname {lg} , j } rceil $ данный как нижняя граница.

Answer 1

Я собираюсь кратко изложить набросок аргумента противника.

Рассмотрим ваш алгоритм отбора, играющий против противника, который мы будем называть противником. Целью противника является предоставление входного $ x $ для вашего алгоритма, который максимизирует количество операций сравнения, выполняемых вашим алгоритмом. Действительно, ваш алгоритм можно рассматривать как дерево сравнения, в котором путь соответствует частичному порядку. Когда алгоритм спрашивает противника о паре $ (x, y) $ элементов, противник возвращает либо $ x <y $ y y <x $. Ответы противника никогда не могут противоречить предыдущим результатам.

Предположим, что крупнейший элемент $ k $-$ x^*$: учитывая частичный порядок, связанный с любым листом дерева сравнения, тогда $ x^*$ должен быть сопоставим с любым другим элементом, чтобы алгоритм был Правильно, так что алгоритм должен был сделать хотя бы одно сравнение $ (y, z) $ $ forall y neq x^*$ leq z <y $. Назовите такое сравнение ключевой Для элемента $ y $. Очевидно, что противник хочет максимизировать количество не важных сравнений, проведенных вашим алгоритмом.

Пусть $ l $ будет набором из самых больших элементов $ K - 1 $; Ваш алгоритм должен правильно идентифицировать все элементы в $ l $, а также самый большой элемент в $ x setminus l $, то есть $ x^*$. Обратите внимание, что каждый элемент в $ x setminus l $ потерял хотя бы одно важное сравнение. Теперь у противника есть стратегия, которая заставляет каждого из элементов $ k - 1 $ в $ l $ выиграть как минимум $ left lceil { lg frac {n} {{k - 1}} right Сравнения rceil $, ни одно из которых не имеет решающего отношения для $ x setminus l $. Добавляя оставшиеся $ n - k $ важные сравнения для $ x setminus l $, вы получите нижнюю границу. Для получения подробной информации, пожалуйста, прочитайте следующее, отлично, Джефф Эриксон заметки.