Limite inferior para encontrar o quinto elemento menor usando argumentos adversos

Em muitos textos, um limite inferior para encontrar $k$ th menor elemento é derivado fazendo uso de argumentos usando medianas. Como posso encontrar alguém usando um argumento adversário?

A Wikipedia diz que o algoritmo do torneio é executado em , e n - k + ∑ n j = n + 2 - k ⌈ $O(n+k\log n)$ édadocomo limite inferior.$n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$

Vou esboçar brevemente um esboço de um argumento adversário.

Considere o seu algoritmo de seleção jogando contra um oponente que chamaremos de adversário. O objetivo do adversário é fornecer uma entrada $X$ para o seu algoritmo que maximize o número de operações de comparação realizadas pelo seu algoritmo. De fato, seu algoritmo pode ser visto como uma árvore de comparação, na qual um caminho corresponde a uma ordem parcial. Quando o algoritmo pergunta ao adversário sobre um par $(x, y)$ de elementos, o adversário retorna $x < y$ ou $y < x$ . As respostas do adversário nunca podem contradizer resultados anteriores.

Suponha que o $k$ ésimo elemento maior seja $x^*$ : considerando a ordem parcial associada a qualquer folha da árvore de comparação, então $x^*$ deve ser comparável a qualquer outro elemento para que o algoritmo esteja correto, de modo que o algoritmo deve ter fez pelo menos uma comparação $(y, z)$ $\forall y \neq x^*$ cujo resultado é $y < z \leq x^*$ ou $x^* \leq z < y$ . Chame essa comparação de crucial para um elemento $y$. Obviamente, o adversário deseja maximizar o número de comparações não cruciais feitas pelo seu algoritmo.

Seja $L$ o conjunto de $k−1$ maiores elementos; seu algoritmo precisa identificar corretamente todos os elementos em $L$ e também o maior elemento em $X \setminus L$ , ou seja, $x^*$ . Observe que cada elemento em $X \setminus L$ perdeu pelo menos uma comparação crucial. Agora, o adversário tem uma estratégia que força cada um dos elementos $k - 1$ em $L$ a vencer pelo menos $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$comparações, nenhum dos quais é crucial para$X \setminus L$. Adicionando ascomparações cruciais$n - k$restantespara$X \setminus L$você obtém o limite inferior. Para detalhes, leia o seguinte, excelente,observaJeff Erikson.