localizando os menores elementos k na matriz em O (k)

Esta é uma pergunta interessante que encontrei na web. Dado um array contendo n números (sem informações sobre eles), devemos pré-processar o array em tempo linear, para que possamos retornar os k menores elementos em O (k), quando recebermos um número 1 <= k <= n

Estive discutindo esse problema com alguns amigos, mas ninguém conseguiu encontrar uma solução; Qualquer ajuda seria apreciada!

notas rápidas: -a ordem dos k menores elementos não é importante -os elementos da matriz são número, podem ser números inteiros e podem não ser (portanto, nenhuma classificação de raiz) -o número k não é conhecido no estágio de pré-processamento. o pré-processamento é O (n) time. a função (encontre k elementos menores) no tempo O (k).

Pré-processe a matriz de valores no tempo O ( n ) :$n$$O(n)$

• $i\leftarrow n$
• enquanto $i>2$
  • Calcule a mediana de A [ 1 .. i ] no tempo O ( i $m$$A[1..i]$$O(i)$
  • partição em Um [ 1 .. i / 2 - 1 ] ≤ m e A [ i / 2 + 1 .. i ] ≥ m no mesmo tempo.$A[1..i]$$A[1..i/2-1] \leq m$$A[i/2+1..i]\geq m$
  • $i \leftarrow \lfloor i/2 \rfloor$

O tempo total é precomputation dentro $O(1+2+4+...+n)\subseteq O(n)$

Responda a uma consulta dos menores elementos em A no tempo O ( k ) :$k$$A$$O(k)$

• $l\leftarrow \lfloor \log_2 k \rfloor$
• selecione o th elemento x de A [ 2 l . .2 l + 1 ] no tempo O ( 2 l ) ⊆ O ( k $(k-2^l)$$x$$A[2^l..2^{l+1}]$$O(2^l)\subseteq O(k)$
• partição por x ao mesmo tempo$A[2^l..2^{l+1}]$$x$

contém os k menores elementos.$A[1..k]$$k$

Referências:

• Em 1999, Dor e Zwick forneceram um algoritmo para calcular a mediana de elementos no tempo dentro de 2,942 n + o ( n ) comparações, o que produz um algoritmo para selecionar o k- ésimo elemento de n elementos não-ordenados em menos de 6 n comparações.$n$$2.942 n + o(n)$$k$$n$$6n$

Suponha por simplicidade que $n = 2^m$ . Use o algoritmo de seleção de tempo linear para encontrar os elementos nas posições ; isso leva tempo linear. Dado k , encontre t tal que 2 t - 1 ≤ k ≤ 2 t ; note que 2 t ≤ 2 k . Filtrar todos os elementos da classificação no máximo 2 $2^{m-1},2^{m-2},2^{m-3},\ldots,1$$k$$t$$2^{t-1} \leq k \leq 2^t$$2^t \leq 2k$$2^t$e agora use o algoritmo de seleção de tempo linear para encontrar o elemento na posição no tempo O ( 2 t ) = O ( k ) .$k$$O(2^t) = O(k)$

Esclarecimento: Pode parecer que o pré-processamento leva tempo , e que é realmente o caso, se você não tiver cuidado. Aqui está como fazer o pré-processamento em tempo linear:$\Theta(n\log n)$

while n > 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2

$n + n/2 + n/4 + \cdots + 1 < 2n$$A$$k$$A[0..n/2^k-1]$$n/2^k$

$O(n)$$O(k)$$k$

Frederickson, Greg N. , Um algoritmo ideal para seleção em um min-heap , Inf. Comput. 104, No. 2, 197-214 (1993). ZBL0818.68065 ..

$k$$k$