kleinste k Elemente im Array in O (k) finden

12

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.

Idan
quelle
4
Wie wäre es mit einem Min-Heap?
Shir
1
Schauen Sie sich k-skyband und top-k-Berechnung an. Die Veröffentlichung cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf enthält eine schöne Übersicht über verwandte Literatur.
András Salamon
1
Shir-ich habe die Min-Heap-Idee untersucht. Um jedoch die k kleinsten Zahlen in min Heap zu drucken, ist in O (klogn) Zeit und nicht O (k) wie erforderlich
Idan
4
@idannik: Warum dauert es Ihrer Meinung nach , um die k kleinsten Elemente in einem Min-Heap zu finden? Ω(klogn)k
Kristoffer Arnsfelt Hansen
8
Ich denke nicht, dass dies Forschungsniveau ist. Es sieht aus wie eine Aufgabe. Wo hast du es gefunden?
Kaveh

Antworten:

24

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

  • in
  • während i>2
    • Berechnen Sie den Median von A [ 1 .. i ] in Zeit O ( i )mA[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/21]mA[i/2+1..i]m
    • ii/2

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

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

  • llog2k
  • wähle das te Element x von A [ 2 l . 0,2 l + 1 ] in der Zeit O ( 2 l ) O ( k )(k2l)xA[2l..2l+1]O(2l)O(k)
  • Trennwand von x in der gleichen ZeitA[2l..2l+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 .n2.942n+o(n)kn6n
Jeremy
quelle
1
Ich vermute, die äußere Schleife soll 'für i in ' sein. Unterscheidet sich Ihr Algorithmus von dem in Yuval Filmus 'Antwort? {2lgn,,4,2,1}
Radu GRIGore
2
Dies ist eine Verallgemeinerung meines Algorithmus auf beliebiges . Es werden auch einige Implementierungsdetails aufgeführt, die in meiner Antwort (absichtlich) weggelassen wurden. n
Yuval Filmus
3
@YuvalFilmus Wollen Sie durch Ihren Kommentar implizieren, dass meine Antwort Ihrer unethisch nahe kommt? Dies ist die Lösung, die mir bei der Prüfung der Frage in den Sinn gekommen ist. Ich habe gesehen, dass Sie ein ähnliches veröffentlicht haben, fand es aber unklar, also habe ich mein eigenes geschrieben (im Gegensatz zu einer größeren Bearbeitung von Ihnen). Entscheidend ist letztendlich die Qualität der Antworten auf die Systeme, nicht wirklich derjenige, der sie geschrieben hat: Die Abzeichen und der Ruf sind nur Anreize, keine Ziele an sich.
Jeremy
4
@ Jeremy Überhaupt nicht; Nur, dass die beiden Lösungen die gleichen sind (aber deine funktioniert für beliebiges ) und dass ich die Details nicht präzisiert habe, falls es sich tatsächlich um eine Hausaufgabenfrage handelte. n
Yuval Filmus
2
Oh :( Tut mir leid, dass dann. (Obwohl ich immer noch denken würde, vollständige Antworten zu geben, hat Vorrang vor Zuweisungsverdacht)
Jeremy
14

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 - 1k 2 t ist ; beachte, dass 2 t2 k ist . Filtern Sie alle Elemente mit einem Rang von höchstens 2 t herausn=2m2m1,2m2,2m3,,1kt2t1k2t2t2k2tVerwenden Sie nun den linearen Zeitauswahlalgorithmus, um das Element an der Position in der Zeit O ( 2 t ) = O ( k ) zu finden .kO(2t)=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:Θ(nlogn)

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++1<2nAkA[0..n/2k1]n/2k

Yuval Filmus
quelle
1
Natürlich. Wenn das Array sortiert ist, können Sie dies in ohne Vorverarbeitung lösen . Vielleicht kennen Sie den linearen Zeitauswahlalgorithmus nicht, der das k -größte Element in der Zeit O ( n ) finden kann ? O(1)kO(n)
Yuval Filmus
4
@Yuval Filmus: Laufen Sie nicht den Algorithmus - mal, für insgesamt n log n Schritte? Oder hatten Sie eine Art Interleaving im Sinn? lognnlogn
András Salamon
3
@ AndrásSalamon: Wenn Sie die Antwort von Jeremy lesen (die für mich fast so aussieht wie diese), sehen Sie, dass Sie zuerst das gesamte Array, dann die erste Hälfte und so weiter verarbeiten.
Radu GRIGore
3
@ AndrásSalamon Radu ist richtig. Nachdem Sie den Median gefunden haben, unterteilen Sie das Array (an Ort und Stelle) in die untere und obere Hälfte und greifen dann auf die untere Hälfte zurück. Die Laufzeit ist dann proportional zu . n+n/2+n/4++1<2n
Yuval Filmus
5
Übrigens erscheint dieser Algorithmus als Unterprogramm in meiner Antwort auf eine frühere Frage: cstheory.stackexchange.com/questions/17378/…
David Eppstein
2

Verwenden Sie zuerst O(n) , um einen Min-Heap zu erstellen. Es ist bekannt, dass wir O(k) , um das k zu findenk 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 ..

hqztrue
quelle
1
Ich verstehe nicht, wie wir die kleinsten Elemente aus einem Min-Heap in der Zeit O ( k ) extrahieren können , da das Entfernen jedes Elements logarithmische Zeit in der Größe des Heap benötigt. Könnten Sie klarstellen, was Sie hier im Sinn hatten? Vielen Dank! kO(k)
a3nm
@ a3nm Es ist zwar kein einfacher Algorithmus, aber ich habe die Referenz aktualisiert.
Freitag,
Entschuldigung, soweit ich dem Hinweis entnehmen kann, dass Sie gerade über die Auswahl des ten kleinsten Elements (dh eines einzelnen Elements, nicht der k kleinsten Elemente) in der Zeit O ( k ) sprechen . Ich verstehe nicht, wie sich dies anpassen würde, um die k kleinsten Elemente zu extrahieren . Könnten Sie vielleicht die Referenz erklären oder aktualisieren? kkO(k)k
a3nm
@ a3nm ja die referenz gibt dir nur das kleinste element x . Wenn Sie dies jedoch wissen, können Sie einfach ein dfs im Heap ausführen, um alle Elemente < x in O ( k ) zu finden . kx<xO(k)
Freitag,
Entschuldigung, ich sehe nicht, welche DFS Sie durchführen würden, um diese Elemente zu finden? (Einige von ihnen sind möglicherweise keine Vorfahren des ten kleinsten Elements im Haufen, dh, soweit ich die Lokalisierung beurteilen kann, ist z. B. das k / 2- te Element, das die Position des k- ten Elements kennt, nicht trivial .)kk/2k
a3nm
0

kk te größte Element als Drehpunkt verwenden.

Apfel
quelle
1
Die ursprüngliche Frage erwähnt das kist zur Zeit der Vorverarbeitung nicht bekannt ....
Jeremy
2
Aha. Mein Fehler.
Jbapple