Límite inferior para encontrar el késimo elemento más pequeño utilizando argumentos adversos

En muchos textos, se deriva un límite inferior para encontrar el elemento más pequeño mediante el uso de argumentos utilizando medianas. ¿Cómo puedo encontrar uno usando un argumento adversario?$k$

Wikipedia dice que el algoritmo del torneo se ejecuta en , y n - k + ∑ n j = n + 2 - k ⌈ $O(n+k\log n)$ sedacomo límite inferior.$n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$

Voy a resumir brevemente un bosquejo de un argumento adversario.

Considere su algoritmo de selección jugando contra un oponente que llamaremos adversario. El objetivo del adversario es proporcionar una entrada $X$ para su algoritmo que maximice el número de operaciones de comparación realizadas por su algoritmo. De hecho, su algoritmo puede verse como un árbol de comparación, en el que una ruta corresponde a un orden parcial. Cuando el algoritmo le pregunta al adversario sobre un par $(x, y)$ de elementos, el adversario devuelve $x < y$ o $y < x$ . Las respuestas adversarias nunca pueden contradecir los resultados anteriores.

Suponga que el $k$ -ésimo elemento más grande es $x^*$ : considerando el orden parcial asociado a cualquier hoja del árbol de comparación, entonces $x^*$ debe ser comparable con cualquier otro elemento para que el algoritmo sea correcto, de modo que el algoritmo debe tener hizo al menos una comparación $(y, z)$ $\forall y \neq x^*$ cuyo resultado es $y < z \leq x^*$ o $x^* \leq z < y$ . Llame a tal comparación crucial para un elemento $y$. Obviamente, el adversario quiere maximizar el número de comparaciones no cruciales realizadas por su algoritmo.

Sea $L$ el conjunto de $k−1$ elementos más grandes; su algoritmo necesita identificar correctamente todos los elementos en $L$ y también el elemento más grande en $X \setminus L$ , es decir, $x^*$ . Observe que cada elemento en $X \setminus L$ ha perdido al menos una comparación crucial. Ahora, el adversario tiene una estrategia que obliga a cada uno de los elementos $k - 1$ en $L$ a ganar al menos $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$comparaciones, ninguno de los cuales es crucial para$X \setminus L$. Agregando las$n - k$comparaciones crucialesrestantespara$X \setminus L$se obtiene el límite inferior. Para más detalles, lea lo siguiente, excelente,señalaJeff Erikson.