Can someone explain LazySelect?
-
31-10-2019 - |
Pergunta
The LazySelect algorithm is given in these slides as follows.
We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element.
- Let $R$ be a set of $n^{3/4}$ elements chosen uniformly at random with replacement from $S$.
- Sort $R$ and find $a$ and $b$ such that $\mathrm{rank}_R(a) = kn^{-1/4} – sqrt(n)$ and $\mathrm{rank}_R(b) = kn^{-1/4} + sqrt(n)$, where $\mathrm{rank}_X(x) = t$ if $x$ is the $t$th smallest element in $X$.
- Compute $\mathrm{rank}_S(a)$ and $\mathrm{rank}_S(b)$: Output
FAIL
if $k < \mathrm{rank}_S(a)$ or $k > \mathrm{rank}_S(b)$. - Let $P = \{i \in S\mid a\le y\le b\}$: Output
FAIL
if $|P| \ge 4n^{3/4}$. - Return the $(k - \mathrm{rank}_S(a) + 1)$th smallest element from $P$.
Can someone explain the intuition behind the algorithm in a way that is more detailed and easier to understand than the slides above?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange