Dolna granica dla znalezienia k-tego najmniejszego elementu za pomocą argumentów przeciwnika

W wielu tekstach wyznacza się dolną granicę dla znalezienia tego najmniejszego elementu za pomocą argumentów wykorzystujących mediany. Jak mogę je znaleźć, używając argumentu przeciwnika?$k$

Wikipedia twierdzi, że algorytm turnieju działa w , a n - k + ∑ n j = n + 2 - k ⌈ $O(n+k\log n)$ jestpodanajako dolna granica.$n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$

Mam zamiar krótko nakreślić szkic argumentu przeciwnika.

$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$. Oczywiście przeciwnik chce zmaksymalizować liczbę nieistotnych porównań przeprowadzanych przez algorytm.

$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$