znajdowanie najmniejszych k elementów w tablicy w O (k)

To interesujące pytanie znalazłem w Internecie. Biorąc pod uwagę tablicę zawierającą n liczb (bez informacji o nich), powinniśmy wstępnie przetworzyć tablicę w czasie liniowym, abyśmy mogli zwrócić k najmniejszych elementów w czasie O (k), gdy otrzymamy liczbę 1 <= k <= n

Dyskutowałem o tym problemie z przyjaciółmi, ale nikt nie mógł znaleźć rozwiązania; każda pomoc będzie mile widziana!

krótkie uwagi: - kolejność k najmniejszych elementów nie jest ważna - elementy w tablicy są liczbą, mogą być liczbami całkowitymi i mogą nie być (więc brak sortowania w radix) - liczba k nie jest znana na etapie wstępnego przetwarzania. przetwarzanie wstępne to czas O (n). funkcja (znajdź k najmniejszych elementów) w czasie O (k).

Przetwórz wstępnie tablicę wartości w czasie O ( n ) :$n$$O(n)$

• $i\leftarrow n$
• podczas gdy $i>2$
  • Obliczyć średnią o A [ 1 .. I ] w czasie O ( I $m$$A[1..i]$$O(i)$
  • Partycja [ 1 .. I ] w A [ 1 .. I / 2 - 1 ] ≤ m i [ i / 2 + 1 .. I ] ≥ m w tym samym czasie.$A[1..i]$$A[1..i/2-1] \leq m$$A[i/2+1..i]\geq m$
  • $i \leftarrow \lfloor i/2 \rfloor$

Całkowity czas precomputation jest w $O(1+2+4+...+n)\subseteq O(n)$

Odpowiedz na zapytanie o najmniejszych elementów w A w czasie O ( k ) :$k$$A$$O(k)$

• $l\leftarrow \lfloor \log_2 k \rfloor$
• wybierz th element x z A [ 2 l . .2 l + 1 ] w czasie O ( 2 l ) ⊆ O ( k $(k-2^l)$$x$$A[2^l..2^{l+1}]$$O(2^l)\subseteq O(k)$
• przegroda przez x w tym samym czasie$A[2^l..2^{l+1}]$$x$

zawiera k najmniejszych elementów.$A[1..k]$$k$

Bibliografia:

• W 1999 roku Dor i Zwick podali algorytm obliczający medianę elementów w czasie w ramach porównań 2.942 n + o ( n ) , co daje algorytm do wyboru k- tego elementu spośród n nieuporządkowanych elementów w mniej niż 6 n porównaniach.$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. , Optymalny algorytm do selekcji w hałdzie min. , Inf. Comput. 104, nr 2, 197–214 (1993). ZBL0818.68065 ..

$k$$k$