kleinste k Elemente im Array in O (k) finden

Dies ist eine interessante Frage, die ich im Internet gefunden habe. Bei einem Array mit n Zahlen (ohne Informationen darüber) sollten wir das Array in linearer Zeit vorverarbeiten, damit wir die k kleinsten Elemente in der O (k) -Zeit zurückgeben können, wenn wir eine Zahl 1 <= k erhalten <= n

Ich habe dieses Problem mit einigen Freunden diskutiert, aber niemand konnte eine Lösung finden. Jede Hilfe wäre dankbar!

Kurznotizen: - Die Reihenfolge der k kleinsten Elemente ist nicht wichtig - Die Elemente im Array sind Zahlen, können ganze Zahlen sein und sind möglicherweise nicht (also keine Grundsortierung) - Die Zahl k ist in der Vorverarbeitungsphase nicht bekannt. Die Vorverarbeitung ist O (n) -Zeit. die Funktion (finde k kleinste Elemente) auf O (k) Zeit.

Verarbeiten Sie das Array von Werten in der Zeit O ( n ) vor :$n$$O(n)$

• $i\leftarrow n$
• während $i>2$
  • Berechnen Sie den Median von A [ 1 .. i ] in Zeit O ( i $m$$A[1..i]$$O(i)$
  • Partition in A [ 1 .. i / 2 - 1 ] ≤ m und A [ i / 2 + 1 .. i ] ≥ m in der gleichen Zeit.$A[1..i]$$A[1..i/2-1] \leq m$$A[i/2+1..i]\geq m$
  • $i \leftarrow \lfloor i/2 \rfloor$

Die Gesamtzeit ist innerhalb precomputation $O(1+2+4+...+n)\subseteq O(n)$

Beantworten Sie eine Anfrage nach den kleinsten Elementen in A in der Zeit O ( k ) :$k$$A$$O(k)$

• $l\leftarrow \lfloor \log_2 k \rfloor$
• wähle das te Element x von A [ 2 l . 0,2 l + 1 ] in der Zeit O ( 2 l ) ≤ O ( k $(k-2^l)$$x$$A[2^l..2^{l+1}]$$O(2^l)\subseteq O(k)$
• Trennwand von x in der gleichen Zeit$A[2^l..2^{l+1}]$$x$

enthält die k kleinsten Elemente.$A[1..k]$$k$

Verweise:

• 1999 gaben Dor und Zwick einen Algorithmus zur Berechnung des Medians von Elementen in der Zeit innerhalb von 2.942 n + o ( n ) Vergleichen an, der einen Algorithmus zur Auswahl des k- ten Elements aus n ungeordneten Elementen in weniger als 6 n Vergleichen liefert .$n$$2.942 n + o(n)$$k$$n$$6n$

Der Einfachheit halber sei . Verwenden Sie den linearen Zeitauswahlalgorithmus, um die Elemente an den Positionen 2 m - 1 , 2 m - 2 , 2 m - 3 , … , 1 zu finden . Dies dauert lineare Zeit. Wenn k gegeben ist , finde t so, dass 2 t - 1 ≤ k ≤ 2 t ist ; beachte, dass 2 t ≤ 2 k ist . Filtern Sie alle Elemente mit einem Rang von höchstens 2 $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$Verwenden Sie nun den linearen Zeitauswahlalgorithmus, um das Element an der Position in der Zeit O ( 2 t ) = O ( k ) zu finden .$k$$O(2^t) = O(k)$

Klarstellung: Es scheint, dass die Vorverarbeitung Zeit in nimmt takes ( n log n ) , und das ist in der Tat der Fall, wenn Sie nicht vorsichtig sind. So führen Sie die Vorverarbeitung in linearer Zeit durch:$\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

Die In-Place-Partitionierung erfolgt wie bei QuickSort. Die Laufzeit ist linear in und somit linear. Am Ende erfüllt das Array A die folgende Eigenschaft: Für jedes k besteht A [ 0 .. n / 2 k - 1 ] aus den n / 2 k kleinsten Elementen.$n + n/2 + n/4 + \cdots + 1 < 2n$$A$$k$$A[0..n/2^k-1]$$n/2^k$

Verwenden Sie zuerst $O(n)$ , um einen Min-Heap zu erstellen. Es ist bekannt, dass wir $O(k)$ , um das k zu finden$k$ kleinsten Elemente in einem Min-Heap zu finden:

Frederickson, Greg N. , Ein optimaler Algorithmus zur Auswahl in einem Min-Heap , Inf. Comput. 104, Nr. 2, 197-214 (1993). ZBL0818.68065 ..

$k$$k$ te größte Element als Drehpunkt verwenden.