trouver les plus petits k éléments du tableau dans O (k)

C'est une question intéressante que j'ai trouvée sur le Web. Étant donné un tableau contenant n nombres (sans aucune information à leur sujet), nous devrions pré-traiter le tableau en temps linéaire afin de pouvoir retourner les k plus petits éléments en temps O (k), quand on nous donne un nombre 1 <= k <= n

J'ai discuté de ce problème avec des amis mais personne n'a pu trouver de solution; Toute aide serait appréciée!

notes rapides: -l'ordre des k plus petits éléments n'est pas important -les éléments dans le tableau sont des nombres, peuvent être des entiers et peuvent ne pas l'être (donc pas de tri radix) -le nombre k n'est pas connu dans la phase de prétraitement. le prétraitement est en temps O (n). la fonction (trouver k plus petits éléments) sur le temps O (k).

Prétraitez le tableau de valeurs dans le temps O ( n ) :$n$$O(n)$

• $i\leftarrow n$
• tandis que $i>2$
  • Calculer la médiane de A [ 1 .. i ] dans le temps O ( i $m$$A[1..i]$$O(i)$
  • partitionner en A [ 1 .. i / 2 - 1 ] ≤ m et A [ i / 2 + 1 .. i ] ≥ m en même temps.$A[1..i]$$A[1..i/2-1] \leq m$$A[i/2+1..i]\geq m$
  • $i \leftarrow \lfloor i/2 \rfloor$

Le temps total de précalcul est à $O(1+2+4+...+n)\subseteq O(n)$

Répondez à une requête pour les plus petits éléments de A dans le temps O ( k ) :$k$$A$$O(k)$

• $l\leftarrow \lfloor \log_2 k \rfloor$
• sélectionner le ème élément x de A [ 2 l . .2 l + 1 ] dans le temps O ( 2 l ) ⊆ O ( k $(k-2^l)$$x$$A[2^l..2^{l+1}]$$O(2^l)\subseteq O(k)$
• partition par x en même temps$A[2^l..2^{l+1}]$$x$

contient les k plus petits éléments.$A[1..k]$$k$

Les références:

• En 1999, Dor et Zwick ont donné un algorithme pour calculer la médiane de éléments dans le temps à l'intérieur de 2,942 n + o ( n ) comparaisons, ce qui produit un algorithme pour sélectionner le k ème élément parmi n éléments non ordonnés dans moins de 6 n comparaisons.$n$$2.942 n + o(n)$$k$$n$$6n$

$n = 2^m$$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$$k$$O(2^t) = O(k)$

$\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. , Un algorithme optimal pour la sélection dans un min-tas , Inf. Comput. 104, n ° 2, 197-214 (1993). ZBL0818.68065 ..

$k$$k$