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

Во многих текстах нижняя граница для нахождения го наименьшего элемента выводится с использованием аргументов, использующих медианы. Как я могу найти один, используя аргумент противника?$k$

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

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

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

Предположим, что $k$ величине элемент равен $x^*$ : учитывая частичный порядок, связанный с любым листом дерева сравнения, тогда $x^*$ должен быть сопоставим с любым другим элементом, чтобы алгоритм был корректным, поэтому алгоритм должен иметь сделал хотя бы одно сравнение $(y, z)$ $\forall y \neq x^*$ , результатом которого является либо $y < z \leq x^*$ либо $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$вы получаете нижнюю границу. Для деталей, пожалуйста, прочитайте следующее, отлично,отмечаетДжефф Эриксон.