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.

  1. Let $R$ be a set of $n^{3/4}$ elements chosen uniformly at random with replacement from $S$.
  2. 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$.
  3. Compute $\mathrm{rank}_S(a)$ and $\mathrm{rank}_S(b)$: Output FAIL if $k < \mathrm{rank}_S(a)$ or $k > \mathrm{rank}_S(b)$.
  4. Let $P = \{i \in S\mid a\le y\le b\}$: Output FAIL if $|P| \ge 4n^{3/4}$.
  5. 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
scroll top